#include "migrations.h"
#include "bits/stdc++.h"
using namespace std;
vector<vector<int>> adj;
vector<int> pow5;
int c1, c2;
int d1, d2;
int globalA, globalB;
void dfs(int cur, int par, vector<vector<int>> &adj, vector<int> &depth, int dep) {
depth[cur] = dep;
for (auto &e : adj[cur])
if (e != par)
dfs(e, cur, adj, depth, dep + 1);
}
pair<int, int> diameter() {
vector<int> depth(10000, 0), depth2(10000, 0);
dfs(0, -1, adj, depth, 0);
int max_depth = 0, end1 = -1, end2 = -1;
for (int i = 0; i < 10000; i++)
if (depth[i] > max_depth)
max_depth = depth[i], end1 = i;
max_depth = 0;
dfs(end1, -1, adj, depth2, 0);
for (int i = 0; i < 10000; i++)
if (depth2[i] > max_depth)
max_depth = depth2[i], end2 = i;
if (end1 > end2)
swap(end1, end2);
return {end1, end2};
}
vector<int> encode(int x, int len) {
vector<int> v(len);
int num = x;
for (int i = len - 1; i >= 0; i--) {
int d = num / pow5[i];
v[i] = d;
num -= d * pow5[i];
}
return v;
}
int decode(vector<int> x) {
int len = x.size();
int ans = 0;
for (int i = len - 1; i >= 0; i--) {
int d = x[i];
ans += d * pow5[i];
}
return ans;
}
vector<pair<int, int>> m;
int encode12(int a, int b) {
for (int i = 0; i < 66; i++)
if (m[i].first == a && m[i].second == b)
return i;
return -1;
}
pair<int, int> decode12(int x) { return m[x]; }
void pre() {
pow5.resize(12, 1);
for (int i = 1; i < 12; i++)
pow5[i] = pow5[i - 1] * 5;
c1 = -1, c2 = -1;
d1 = -1, d2 = -1;
for (int i = 0; i < 11; i++) {
for (int j = i + 1; j < 12; j++) {
m.push_back({i, j});
}
}
adj.resize(10000, vector<int>());
}
void one(int x, int y, int &d1, int &d2, int &C) {
if (d1 == x && d2 == y)
C = 0;
else if (d1 == x)
C = 1;
else
C = 2;
}
void two(int x, int y, int v, int &d1, int &d2, int &C) {
if (d2 != 9999) {
if (((d1 == x && d2 == v) || (d1 == v && d2 == x)))
C = 0;
else
C = 1;
} else {
if (d1 == x)
C = 2;
else if (d1 == y)
C = 3;
else
C = 4;
}
}
int send_message(int N, int i, int Pi) {
if (i == 1)
pre();
if (i <= 9981) {
adj[i].push_back(Pi);
adj[Pi].push_back(i);
return 0;
}
if (i <= 9993) {
if (c1 == -1) {
int u, v;
tie(u, v) = diameter();
c1 = u, c2 = v;
}
adj[i].push_back(Pi);
adj[Pi].push_back(i);
int V = 9999 * c1 + c2;
vector<int> enc = encode(V, 12);
return enc[i - 9982];
}
if (i <= 9996) {
if (d1 == -1) {
int u, v;
tie(u, v) = diameter();
d1 = u, d2 = v;
}
adj[i].push_back(Pi);
adj[Pi].push_back(i);
int V;
if (c1 == d1 && c2 == d2)
V = 124;
else if (c1 == d1)
V = 70 + d2 - 9982;
else if (d1 == c2)
V = 90 + d2 - 9982;
else
V = encode12(d1, d2);
vector<int> enc = encode(V, 3);
if (i == 9996)
c1 = d1, c2 = d2;
return enc[i - 9994];
}
if (i == 9997) {
adj[i].push_back(Pi);
adj[Pi].push_back(i);
int u, v;
tie(u, v) = diameter();
int A;
if ((u == c1 && v == c2) || (u == c1 && v == 9994) ||
(u == c1 && v == 9995))
A = 0;
else if ((u == c1 && v == 9996) || (u == c1 && v == 9997) ||
(u == c2 && v == 9994))
A = 1;
else if ((u == c2 && v == 9995) || (u == c2 && v == 9996) ||
(u == c2 && v == 9997))
A = 2;
else if ((u == 9994 && v == 9995) || (u == 9994 && v == 9996) ||
(u == 9994 && v == 9997))
A = 3;
else
A = 4;
globalA = A;
return A;
}
if (i == 9998) {
adj[i].push_back(Pi);
adj[Pi].push_back(i);
int u, v;
tie(u, v) = diameter();
int A = globalA, B;
if (A == 0) {
if ((u == c1 && v == c2))
B = 0;
else if ((u == c1 && v == 9994))
B = 1;
else if ((u == c1 && v == 9995))
B = 2;
else if ((u == c1 && v == 9998) || (u == c2 && v == 9998))
B = 3;
else
B = 4;
} else if (A == 1) {
if ((u == c1 && v == 9996))
B = 0;
else if ((u == c1 && v == 9997) || (u == c1 && v == 9998))
B = 1;
else if ((u == c2 && v == 9994))
B = 2;
else if ((u == c2 && v == 9998) || (u == 9996 && v == 9998))
B = 3;
else
B = 4;
} else if (A == 2) {
if ((u == c2 && v == 9995))
B = 0;
else if ((u == c2 && v == 9996))
B = 1;
else if ((u == c2 && v == 9997))
B = 2;
else if ((u == c2 && v == 9998) || (u == 9995 && v == 9998))
B = 3;
else
B = 4;
} else if (A == 3) {
if ((u == 9994 && v == 9995))
B = 0;
else if ((u == 9994 && v == 9996))
B = 1;
else if ((u == 9994 && v == 9997))
B = 2;
else if ((u == 9994 && v == 9998) || (u == 9995 && v == 9998))
B = 3;
else
B = 4;
} else {
if ((u == 9995 && v == 9996))
B = 0;
else if ((u == 9995 && v == 9997))
B = 1;
else if ((u == 9996 && v == 9997))
B = 2;
else if ((u == 9995 && v == 9998))
B = 3;
else
B = 4;
}
d1 = u, d2 = v;
globalB = B;
return B;
}
adj[i].push_back(Pi);
adj[Pi].push_back(i);
int u = d1, v = d2;
tie(d1, d2) = diameter();
int A = globalA, C;
if (A == 0) {
if ((u == c1 && v == c2))
one(c1, c2, d1, d2, C);
else if ((u == c1 && v == 9994))
one(c1, 9994, d1, d2, C);
else if ((u == c1 && v == 9995))
one(c1, 9995, d1, d2, C);
else if ((u == c1 && v == 9998) || (u == c2 && v == 9998))
two(c1, c2, 9998, d1, d2, C);
else
two(9994, 9995, 9998, d1, d2, C);
} else if (A == 1) {
if ((u == c1 && v == 9996))
one(c1, 9996, d1, d2, C);
else if ((u == c1 && v == 9997) || (u == c1 && v == 9998))
two(9997, 9998, c1, d1, d2, C);
else if ((u == c2 && v == 9994))
one(c2, 9994, d1, d2, C);
else if ((u == c2 && v == 9998) || (u == 9996 && v == 9998))
two(c2, 9996, 9998, d1, d2, C);
else
two(9994, 9997, 9998, d1, d2, C);
} else if (A == 2) {
if ((u == c2 && v == 9995))
one(c2, 9995, d1, d2, C);
else if ((u == c2 && v == 9996))
one(c2, 9996, d1, d2, C);
else if ((u == c2 && v == 9997))
one(c2, 9997, d1, d2, C);
else if ((u == c2 && v == 9998) || (u == 9995 && v == 9998))
two(c2, 9995, 9998, d1, d2, C);
else
two(9996, 9997, 9998, d1, d2, C);
} else if (A == 3) {
if ((u == 9994 && v == 9995))
one(9994, 9995, d1, d2, C);
else if ((u == 9994 && v == 9996))
one(9994, 9996, d1, d2, C);
else if ((u == 9994 && v == 9997))
one(9994, 9997, d1, d2, C);
else if ((u == 9994 && v == 9998) || (u == 9995 && v == 9998))
two(9994, 9995, 9998, d1, d2, C);
else
two(9996, 9997, 9998, d1, d2, C);
} else {
if ((u == 9995 && v == 9996))
one(9995, 9996, d1, d2, C);
else if ((u == 9995 && v == 9997))
one(9995, 9997, d1, d2, C);
else if ((u == 9996 && v == 9997))
one(9996, 9997, d1, d2, C);
else if ((u == 9995 && v == 9998))
one(9995, 9998, d1, d2, C);
else
two(9996, 9997, 9998, d1, d2, C);
}
return C;
}
// end of part 1 //
pair<int, int> rone(int x, int y, int C) {
if (C == 0)
return {x, y};
else if (C == 1)
return {x, 9999};
else
return {y, 9999};
}
pair<int, int> rtwo(int x, int y, int v, int C) {
if (C == 0)
return {min(x, v), max(x, v)};
else if (C == 1)
return {min(y, v), max(y, v)};
else if (C == 2)
return {x, 9999};
else if (C == 3)
return {y, 9999};
else
return {v, 9999};
}
pair<int, int> longest_path(vector<int> S) {
pre();
vector<int> part1(12);
for (int i = 9982; i <= 9993; i++)
part1[i - 9982] = S[i];
int V = decode(part1);
int c1 = (V - (V % 9999)) / 9999, c2 = V % 9999;
vector<int> part2(3);
for (int i = 9994; i <= 9996; i++)
part2[i - 9994] = S[i];
V = decode(part2);
if (V <= 67) {
int u, v;
tie(u, v) = decode12(V);
c1 = u + 9982, c2 = v + 9982;
} else if (V < 90) {
c2 = V + 9982 - 70;
} else if (V < 120) {
c1 = V + 9982 - 90;
swap(c1, c2);
} else {
}
int A = S[9997], B = S[9998], C = S[9999];
if (A == 0) {
if (B == 0)
return rone(c1, c2, C);
else if (B == 1)
return rone(c1, 9994, C);
else if (B == 2)
return rone(c1, 9995, C);
else if (B == 3)
return rtwo(c1, c2, 9998, C);
else
return rtwo(9994, 9995, 9998, C);
} else if (A == 1) {
if (B == 0)
return rone(c1, 9996, C);
else if (B == 1)
return rtwo(9997, 9998, c1, C);
else if (B == 2)
return rone(c2, 9994, C);
else if (B == 3)
return rtwo(c2, 9996, 9998, C);
else
return rtwo(9994, 9997, 9998, C);
} else if (A == 2) {
if (B == 0)
return rone(c2, 9995, C);
else if (B == 1)
return rone(c2, 9996, C);
else if (B == 2)
return rone(c2, 9997, C);
else if (B == 3)
return rtwo(c2, 9995, 9998, C);
else
return rtwo(9996, 9997, 9998, C);
} else if (A == 3) {
if (B == 0)
return rone(9994, 9995, C);
else if (B == 1)
return rone(9994, 9996, C);
else if (B == 2)
return rone(9994, 9997, C);
else if (B == 3)
return rtwo(9994, 9995, 9998, C);
else
return rtwo(9996, 9997, 9998, C);
} else {
if (B == 0)
return rone(9995, 9996, C);
else if (B == 1)
return rone(9995, 9997, C);
else if (B == 2)
return rone(9996, 9997, C);
else if (B == 3)
return rone(9995, 9998, C);
else
return rtwo(9996, 9997, 9998, C);
}
}
