1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
#include <cstdio>
#include <vector>
#include <map>
#include <algorithm>
#include <set>
#include <deque>

#include "kollib.h"
#include "message.h"

#define REP(i, n) for (int i = 0; i < (n); ++i) 
#define FOR(i, a, b) for (int i = (a); i < (b); ++i) 

using namespace std;
const int RRR[] = {
88890109, 903783707, 982657720, 161272446, 414687930, 917985948, 320895246, 830861835, 645296566, 819332700, 770604821, 414408921, 797294010, 326719521, 54514641, 120059782, 836048989, 353226051, 968838246, 922140150, 129717269, 329287767, 128891266, 330259379, 937176148, 270531529, 267087705, 654929368, 758880170, 3471291, 471746389, 82686357, 820140663, 164877316, 33363123, 963005490, 255319243, 279298536, 199603926, 244119599, 215157100, 757663243, 242236877, 508339237, 952987881, 605213372, 770139796, 813941036, 550504981, 98707827, 169946427, 662297448, 373074228, 15002142, 343086103, 170999191, 157818349, 550196067, 144599044, 494539169, 515145303, 306144265, 300356234, 438683716, 176837793, 478118118, 756191519, 869495161, 613081678, 931670840, 976564686, 59457031, 626228617, 642959489, 977243565, 203634036, 847589543, 255302806, 396666, 248711612, 92360512, 346014718, 747787905, 287458607, 430461409, 900937682, 595251670, 143398260, 567639923, 189465530, 233020124, 153219224, 612800843, 963784807, 985608950, 420707437, 711906239, 125703966, 822081064, 727860521, 130600633, 166562702, 887810266, 558001475, 964246038, 255322091, 836331015, 753044327, 254333623, 634392069, 773158446, 13743498, 123840900, 951355763, 129191293, 581395161, 492384410, 697463074, 434056942, 584022675, 523636452, 876061212, 154203129, 633949839, 966106589, 137102425, 607905313, 175038341, 883526953, 120501362, 261543871, 199857036, 782448155, 186418212, 970808685, 134426251, 547791871, 241458237, 273911018, 881041091, 148334854, 752247672, 416981039, 954252793, 610795172, 262398931, 186991475, 686929884, 215118021, 677702293, 979445473, 98755740, 220554343, 220810627, 436254789, 928800399, 850376898, 81502424, 391971854, 447725420, 368668843, 66147147, 419039057, 939081014, 456053570, 291825185, 139614989, 476015334, 944346956, 409716748, 815801934, 782857546, 115109029, 470379427, 989657180, 65348957, 251644470, 918108724, 461995210, 972266909, 240187478, 383236382, 280095956, 38748856, 284114251, 359963048, 755939510, 864101409, 326323697, 568952342, 261045663, 83790429, 340616028, 444640752, 410048367, 944150256, 215754508, 116834360, 163116287, 995968349, 729834520, 822710539, 354285868, 692275658, 353713901, 435561690, 596985711, 67212013, 93168313, 862090067, 648333986, 336655549, 27034906, 746218215, 324549085, 760243165, 501317724, 29971273, 346401527, 742889065, 424826013, 529593673, 131692251, 769813011, 983588122, 558875584, 975482173, 103195829, 136344586, 374111573, 979510965, 716455330, 693090548, 115590085, 544570170, 61848517, 142827051, 683370331, 786238444, 245530904, 666410552, 187056784, 252031488, 767431713, 989246354, 953965182, 508128687, 944245304, 26045410, 429669220, 965562874, 731593156, 365849059, 149853679, 165867181, 74764717, 671793333, 477615250, 88390519, 9147155, 939583614, 786554920, 519880745, 871656237, 995503687, 241510562, 754324083, 844696781, 96548455, 277722928, 129084605, 503369958, 500238593, 691015495, 931276442, 482974217, 82521121, 876701712, 580487734, 710953263, 430935925, 348957470, 29955165, 427594276, 750926343, 547012769, 107725609, 704612363, 653850082, 448320623, 485936890, 259885264, 137216856, 692195676, 154098586, 938974236, 620647353, 44442892, 210543616, 251113382, 891396325, 588433453, 111705290, 109497466, 681532750, 181496472, 707750487, 220502991, 282228313, 554553270, 595444274, 923168766, 380182538, 849383582, 403597882, 764157856, 719183767, 911571155, 996566047, 550680792, 224831471, 910693697, 255012222, 676318890, 303092076, 934003616, 498198731, 511794205, 673825005, 872165679, 275325364, 301658334, 904111961, 6170093, 131379146, 607499877, 458863861, 525128704, 33537952, 943662775, 808309328, 433103344, 892359922, 491073365, 264250708, 147523201, 895843275, 721123128, 242813881, 12640285, 224813341, 413284118, 185406348, 992817349, 146637598, 430157509, 389076567, 395837960, 218434337, 451459826, 651354728, 913892517, 467184371, 6660407, 735511309, 485924552, 404332501, 13724678, 357606882, 639059543, 35401650, 703272672, 346514610, 487643490, 580230529, 75123313, 267112456, 143483356, 942913212, 224821727, 875942019, 92783369, 148375599, 860133976, 999962985, 44173315, 210655998, 752088350, 148737267, 43262982, 339179205, 69993731, 722015581, 170609285, 854812592, 117033868, 954352814, 866623435, 791198953, 571988375, 698015834, 394648840, 68163600, 644788998, 411669314, 25730100, 722466242, 158032824, 202091044, 152949167, 207748980, 958691930, 847847868, 645802517, 120973132, 761205688, 769823751, 768732661, 246089653, 905838843, 742998414, 955270866, 53765004, 182770360, 390339843, 976462499, 150471215, 993893207, 953862684, 217739905, 212650944, 453127884, 13752115, 247401788, 304195862, 443949580, 617056446, 832768987, 654922578, 218463562, 359036152, 582195083, 59052228, 530844124, 743197371, 728102555, 837951102, 235155489, 509077467, 305548429, 662288539, 866762304, 733460373, 45408668, 855033932, 407093747, 25272255, 720453933, 924306734, 769327892, 466138486, 572827250, 366503536, 419489485, 453449447, 859958814, 248299208, 654997484, 826616321, 343736230, 116444710, 696051409, 567549970, 97153578, 393880365, 51234421, 184403674, 556448661, 277878528, 321277452, 601574411, 364662003, 564706520, 37041191, 203231185, 640229676, 990086351, 375961846, 707647819, 950168365, 439426098, 576734535, 892958118, 900709509, 243046726, 482432267, 3359600, 720011251, 260336409, 425185700, 360854028, 659151900, 295762581, 842974004, 355068972, 132870190, 522387808, 930770910, 777071730, 697564783, 641092900, 339459085, 647692995, 844799007, 967240769, 270631391, 891727570, 910975388, 163780469, 196118658, 490766368, 891708856, 849647413, 288709388, 940566448, 604077121, 493000624, 89995207, 403161099, 683822080, 994558994, 207167595, 778210293, 629300660, 973327388, 600990128, 252523208, 531820970, 666399948, 279498697, 503082157, 887639716, 224133302, 605724194, 188111259, 750970591, 567405893, 946634840, 562878327, 616672643, 461005254, 522959917, 538245353, 736708078, 899726426, 488333035, 449695681, 612905847, 249400450, 156816495, 316424877, 74860120, 416102175, 182542220, 892313659, 326216690, 418270270, 165699011, 624214076, 985838638, 665914459, 769780536, 608161614, 346545551, 708752830, 405315166, 551521495, 978560802, 97758078, 906901277, 631141088, 588486335, 232071526, 315172509, 321473883, 41161983, 940399565, 550049904, 988964958, 296767391, 434704150, 457666568, 91117962, 783678095, 741979425, 899071309, 723982981, 635704607, 285354459, 380041058, 155388086, 261172982, 947230021, 416729737, 86278371, 926769928, 288299895, 913179966, 889187370, 189350793, 137844325, 69303232, 575537358, 904871261, 326630644, 247848723, 794710857, 299761530, 763556882, 956364551, 477818126, 292528143, 446921635, 451139608, 536652691, 352026071, 864900089, 346011260, 632172512, 874158636, 75550584, 809884607, 967623358, 839107674, 444773245, 296583728, 901054107, 310420190, 203204391, 542580204, 335890121, 723214565, 193924400, 637420267, 458733852, 522793608, 931463844, 860889437, 918434968, 803371894, 993437371, 668362616, 577680772, 182621851, 535741946, 369259380, 695430109, 856126883, 755827628, 536962198, 132429746, 315864736, 214150698, 917565621, 489862835, 310079645, 872973500, 213440959, 410923929, 530824592, 694919237, 51901469, 589165773, 406883078, 86882747, 144788801, 345598515, 264038536, 301695823, 892127188, 286420363, 199869495, 899368235, 649871542, 527147797, 844201310, 579342074, 973479642, 166520591, 665893009, 77544659, 314932093, 409515972, 627726721, 856896087, 658540210, 320991100, 499487678, 329106249, 728844432, 677708692, 227107941, 646739050, 213996329, 428161762, 966593059, 912248672, 186412955, 773734071, 760522610, 569207483, 337895052, 792684625, 971806335, 408449105, 209716307, 586513952, 753100269, 541524594, 379043959, 344502238, 749848226, 471575729, 440485974, 479190184, 654567617, 634476151, 200878945, 753953378, 564007861, 124330749, 427418155, 574020435, 840718202, 874189539, 298101130, 739026739, 983323021, 220620137, 320293009, 84016858, 866571102, 133432676, 249400340, 286811004, 297685862, 355921041, 205699705, 956853109, 385092117, 66953043, 277243482, 443357973, 697991480, 184315935, 695176145, 721475797, 200946463, 425400349, 872299402, 159663480, 86282652, 35391575, 733107668, 839721400, 348836112, 389055139, 705116247, 952932718, 17604087, 304279108, 9269581, 383992589, 896964337, 974322452, 716363474, 375247165, 411852859, 830433522, 727183795, 560400372, 128113071, 6464012, 137062202, 839761923, 675369541, 773662468, 565782650, 103852684, 856756673, 41100606, 889419837, 581529029, 457573451, 433809107, 737400576, 164145613, 580884665, 768367108, 294401357, 710248714, 38340419, 900815689, 524710942, 896135221, 99143094, 308159059, 420637149, 974070478, 227612352, 279034501, 870462415, 960225649, 718688099, 338488373, 581319986, 377908405, 22967796, 350181973, 967828663, 383483774, 691829116, 290208605, 445248205, 297995376, 839715474, 520965948, 808987553, 799701336, 541689296, 985378447, 49842046, 990816329, 248460628, 672529688, 661495007, 110115974, 217966088, 862838297, 17338964, 779863556, 807370486, 649372447, 999248003, 158137325, 639881456, 384181597, 206871891, 198998326, 204992991, 100722975, 238180273, 943939208, 759445905, 202015999, 486261958, 594753909, 320307535, 592870673, 723574452, 221388552, 497152206, 555120277, 147818457, 791572119, 639336828, 236930102, 251981752, 934380778, 139162313, 720275013, 598439159, 308423903, 864397833, 844725253, 184020843, 994566109, 958259037, 63062636, 365908034, 101889577, 234579449, 518462888, 856464458, 440794174, 478663259, 895167689, 489439345, 413080692, 123264657, 271881007, 450174887, 284829315, 471248250, 794847396, 439516690, 408208929, 250321642, 222465168, 58108482, 564669906, 521910774, 46675538, 438890421, 217282739, 630937552, 911237393, 751088433, 418337640, 217166007, 931059348, 793777862, 968259341, 717668179, 805993884, 212527987, 207518999, 599877191, 447415282, 826179534, 440199618, 475303528, 920271986, 981539388, 298322295, 473551381, 252680823, 645773020, 688040411, 914397593, 347223025, 13687359, 25350387, 797919565, 263065291, 177711036, 987356153, 909931926, 137366956, 715571664, 111653680, 980474311, 682012026, 762679933, 298406314, 901130857, 251858137, 615505058, 941366867, 29148762, 833133141, 99971861, 275227173, 647986732, 137837490, 508295576, 708564774, 139983368, 618330838, 940048365, 181859275, 819630649, 661855364, 306991344, 38620786, 493404308, 105432436, 485692897, 328472058, 917994165, 589811858, 32530680, 813500799, 151210358, 540751608, 134899256, 331603362, 580450825, 720137145, 773112678, 593036402, 240967290, 47757730, 200158694, 509383443, 581687863, 347770515, 21247834, 830090551, 246996280, 496248115, 771411882, 826818678, 447149080, 858555426, 909698050, 291099346, 796522391, 462390841, 108841581, 992540666, 565945915, 665049165, 559378294, 813422680, 695952889, 252718273, 954885428, 600987945, 356587888, 645497135, 979771873, 874196860, 14333444, 82475530, 253332102, 7287059, 460337370, 227246307, 735275279, 267159630, 636096267, 118188003, 738744090, 982889553, 119812591, 746282743, 213965550, 797798632, 149934479, 370070293, 402639998, 947951287, 939521539, 865550540, 573476380, 839096054, 361690682, 220702318, 344810030, 884578891, 373250672, 313672838, 612567772, 914218794, 73035613, 270842155, 413702399, 708051951, 541487203, 96675613, 652371795, 59057005, 451247313, 265398363, 64027647, 326370043, 925856733, 802714599, 876853374, 570361650, 186303697, 871787767, 631942812, 104428114, 401355960, 211711911, 709871614, 822894003, 985056703, 258423467, 463986383, 946415853, 295262859, 815719457, 513903101, 447083470, 471370726, 97837818, 776029897, 754313560, 423813417, 71450172, 386930298, 401162462, 387362462, 83919436, 884777588, 209866589, 205932956, 690974876, 801840265, 725072076, 50895644, 443324307, 70423401, 51696352, 658190769, 168763735, 981482338};

// === Communication ===
const int ALL_DONE = -1;

struct ShardIn {
    int start, dir;
    bool receive() {
        Receive(0);
        start = GetInt(0);
        if (start == ALL_DONE) {
            //printf("received all done from master\n");
            return false;
        }
        dir = GetInt(0);
        //printf("received (%d, %d) from master\n", start, dir);
        return true;
    }

    void send(int target) {
        //printf("Sending (%d, %d) to %d\n", start, dir, target);
        PutInt(target, start);
        PutInt(target, dir);
        Send(target);
    }

    static void send_all_done(int target) {
        PutInt(target, ALL_DONE);
        Send(target);
    }

    bool operator<(const ShardIn& x) const {
        if (start != x.start) return start < x.start;
        return dir < x.dir;
    }
};

struct ShardOut {
    int start, stop, len, dir_start, dir_stop;
    void send() {
        //printf("Sending (%d, %d, %d, %d, %d) to master\n", start, stop, len, dir_start, dir_stop);
        PutInt(0, start);
        PutInt(0, stop);
        PutInt(0, len);
        PutInt(0, dir_start);
        PutInt(0, dir_stop);
        Send(0);
    }

    int receive() {
        int target = Receive(-1);
        start = GetInt(target);
        stop = GetInt(target);
        len = GetInt(target);
        dir_start = GetInt(target);
        dir_stop = GetInt(target);
        //printf("Received (%d, %d, %d, %d, %d) from %d\n", start, stop, len, dir_start, dir_stop, target);
        return target;
    }
};

// === Common ===
int n, m;
set<int> shard_points;
vector<int> q_from, q_to;

void init_common() {
    n = NumberOfStudents();
    m = NumberOfQueries();

    FOR(i, 1, m+1) {
        int from = QueryFrom(i);
        int to = QueryTo(i);

        q_from.push_back(from);
        q_to.push_back(to);

        shard_points.insert(from);
        shard_points.insert(to);
    }

    int idx = 0;
    int limit = (1000 - NumberOfNodes()) / 2 - 3;
    while (idx < 1000 and shard_points.size() < limit) {
        shard_points.insert((RRR[idx++] % n) + 1);
    }
}

// === Master ===
struct edge {
    int to, len;
    edge() : to(-1), len(-1) {}
    edge(int x, int y) : to(x), len(y) {}
};

map<int, edge> results[2];

void save_out(const ShardOut& out, set<ShardIn> shards) {
    {  // Usun duplikat
        ShardIn in;
        in.start = out.stop;
        in.dir = out.dir_stop;
        shards.erase(in);
    }

    results[out.dir_start][out.start] = edge(out.stop, out.len);
    results[out.dir_stop][out.stop] = edge(out.start, out.len);
}

void solve() {
    // Zakladam, ze mam wszystkie wyniki
    // FIXME: wsparcie dla czesciowych wynikow
    map<int, int> nr;
    int start = *shard_points.begin();
    nr[start] = 0;

    int x = start;
    int prev_x = -1;
    int pos = 0;
    while (true) {
        edge e = results[0][x];
        if (e.to == prev_x) e = results[1][x];

        if (e.to == start) break;

        pos += e.len;
        nr[e.to] = pos;
        
        prev_x = x;
        x = e.to;
    }

    REP(i, m) {
        int a = nr[q_from[i]];
        int b = nr[q_to[i]];
        if (a > b) swap(a, b);
    
        //printf("query %d %d = %d %d\n", q_from[i], q_to[i], a, b);
        printf("%d\n", min(b-a, n-b+a));
    }
}

void doMaster() {
    set<ShardIn> shards;
    for (auto x : shard_points) {
        ShardIn in;
        in.start = x;
        in.dir = 0;
        shards.insert(in);
        in.dir = 1;
        shards.insert(in);
    }

    int running = 0;
    FOR(i, 1, NumberOfNodes()) {
        if (shards.empty()) {
            ShardIn::send_all_done(i);
            continue;
        }

        // TODO: lepsza kolejnosc shardow
        ShardIn shard = *shards.begin();
        shards.erase(shards.begin());

        shard.send(i);
        running += 1;
    }

    while (running) {
        ShardOut out;
        int node = out.receive();

        save_out(out, shards);

        if (shards.empty()) {
            ShardIn::send_all_done(node);
            running -= 1;
        } else {
            ShardIn shard = *shards.begin();
            shards.erase(shards.begin());

            shard.send(node);
        }
    }

    solve();
}

// === Worker ===
ShardOut process_shard(const ShardIn& in) {
    ShardOut out;
    out.start = in.start;
    out.dir_start = in.dir;

    int len = 1;
    int x;
    if (in.dir == 0) {
        x = FirstNeighbor(in.start);
    } else {
        x = SecondNeighbor(in.start);
    }

    int prev_x = in.start;
    while (shard_points.find(x) == shard_points.end()) {
        // TODO: sprawdz, czy warto przerwac
        int nx = FirstNeighbor(x);
        if (nx == prev_x) nx = SecondNeighbor(x);
        prev_x = x;
        x = nx;
        len += 1;
    }

    out.len = len;
    out.stop = x;
    out.dir_stop = prev_x == SecondNeighbor(x);
    return out;
}

void doWorker() {
    int dir = 0;
    while (true) {
        // TODO: Pierwszy shard mozna bez mastera.
        ShardIn in;
        if (!in.receive()) break;

        ShardOut out = process_shard(in);
        out.send();
    }
}

// === Main ===
int main() {
    init_common();

    if (MyNodeId() == 0) {
        doMaster();
    } else {
        doWorker();
    }
    
    return 0;
}