#include "kollib.h"
#include "message.h"
#include <iostream>
#include <cassert>
#include <vector>
#define MP make_pair
#define PB push_back
using namespace std;
typedef long long ll;
const int kMaxQ = 404;
int que[kMaxQ];
int pos[kMaxQ];
const int kRange = 1813632;
vector<pair<int, int> > hash_que[kRange];
const int kMaxInst = 1e2 + 4;
int st[kMaxInst];
struct HashPlace {
int pos;
int ind;
HashPlace (int start_, int ind_) : pos(start_), ind(ind_) {}
HashPlace () : pos(0), ind(0) {}
};
HashPlace hash_starts[kRange];
bool Check(int act_v) {
return hash_starts[act_v % kRange].pos == act_v;
}
vector<HashPlace> hash_queries[kRange];
int died[kMaxInst];
struct Edge {
int nei;
int len;
vector<pair<int, int> > found_q;
Edge(int n_, int l_, vector<pair<int, int> >& f_) : nei(n_), len(l_), found_q(f_) {}
};
vector<Edge> edges[kMaxInst];
int vis[kMaxInst];
void Dfs(int v, int dis_from_start, int dep) {
vis[v] = 1;
for (auto& e : edges[v]) {
if (!vis[e.nei] || (e.nei == 0 && dep > 1)) {
for (auto p : e.found_q) {
pos[p.first] = dis_from_start + p.second;
}
Dfs(e.nei, dis_from_start + e.len, dep + 1);
}
}
}
int main() {
//cerr<<"j"<<endl;
int n = NumberOfStudents();
int inst_num = min(n, NumberOfNodes());
int inst = MyNodeId();
if (inst >= inst_num) {
return 0;
}
ll s, a, b, k;
s = 127654389 % n;
a = 364995323;
b = 837322103;
// if (inst == 0) {
// cout<<n<<endl;
// }
for (int i = 0; i < inst_num; i++) {
s = ((a * s) + b) % n;
st[i] = s + 1;
while (hash_starts[st[i] % kRange].pos) {
st[i] = st[i] % n + 1;
}
// if (inst == 0) {
// cout<<st[i]<<" ";
// }
hash_starts[st[i] % kRange] = HashPlace(st[i], i);
}
// if (inst == 0) {
// cout<<endl;
// }
//cerr<<inst<<" starts from "<<st[inst]<<endl;
int q_num = NumberOfQueries();
for (int i = 1; i <= q_num; i++) {
que[2 * i - 1] = QueryFrom(i);
que[2 * i] = QueryTo(i);
//cerr<<que[2 * i - 1]<<" "<<que[2 * i]<<endl;
}
for (int i = 1; i <= 2 * q_num; i++) {
hash_queries[que[i] % kRange].PB(HashPlace(que[i], i));
}
int act_v = st[inst];
int fir = FirstNeighbor(act_v);
int sec = SecondNeighbor(act_v);
int beg[] = {fir, sec};
for (int phase = 0; phase <= 1; phase++) {
vector<pair<int, int> > found_q;
int prev_v = st[inst];
act_v = st[inst];
for (auto p : hash_queries[act_v % kRange]) {
if (p.pos != act_v) {
continue;
}
//cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
found_q.push_back(MP(p.ind, 0));
}
act_v = beg[phase];
int act_dis = 1;
while (!Check(act_v)) {
for (auto p : hash_queries[act_v % kRange]) {
if (p.pos != act_v) {
continue;
}
//cerr<<"Proces nr "<<inst<<" znalazl "<<p.ind<<"-te q tzn. "<<p.pos<<endl;
found_q.push_back(MP(p.ind, act_dis));
}
int new_v = FirstNeighbor(act_v) + SecondNeighbor(act_v) - prev_v;
prev_v = act_v;
act_v = new_v;
act_dis++;
}
int end_in = hash_starts[act_v % kRange].ind;
assert(st[end_in] == act_v);
PutInt(0, inst);
PutInt(0, end_in);
PutInt(0, act_dis);
PutInt(0, found_q.size());
for (auto p : found_q) {
//cerr<<"Hejka"<<inst<<endl;
PutInt(0, p.first);
PutInt(0, p.second);
}
Send(0);
}
if (inst != 0) {
return 0;
}
int max_len = 0;
for (int i = 0; i < inst_num; i++) {
if (died[i]) {
continue;
}
for (int zz = 1; zz <= 2; zz++) {
Receive(i);
int a = GetInt(i);
int b = GetInt(i);
int len = GetInt(i);
max_len = max(max_len, len);
//cout<<len<<endl;
int found_q_num = GetInt(i);
//cerr<<"czytam message (od "<<i<<") "<<a<<" "<<b<<" "<<len<<" "<<found_q_num<<endl;
vector<pair<int, int> > found_q;
for (int j = 0; j < found_q_num; j++) {
int fir = GetInt(i);
int sec = GetInt(i);
//cerr<<"znalezione "<<fir<<" "<<sec<<endl;
found_q.PB(MP(fir, sec));
}
edges[a].PB(Edge(b, len, found_q));
}
}
Dfs(0, 0, 0);
cerr<<1.0 * max_len / n<<endl;
/* for (int i = 1; i <= 2 * q_num; i++) {
cout<<pos[i]<<" ";
}
cout<<endl; */
for (int i = 1; i <= q_num; i++) {
int diff = abs(pos[2 * i - 1] - pos[2 * i]);
//cout<<min(diff, n - diff)<<endl;
}
return 0;
}