#include "migrations.h"
#include "bits/stdc++.h"
using namespace std;
vector<vector<int>> adj123;
vector<int> pow5123;
int c1, c2;
int d1, d2;
#define upd {adj123[i].push_back(Pi); adj123[Pi].push_back(i);}
#define P123(k, l) (u == k && v == l)
#define Q123(k, l) ((d1 == k && d2 == l) || (d1 == l && d2 == k))
const int p123 = 9994, q123 = 9995, r123 = 9996;
const int a123 = 9997, b123 = 9998, c123 = 9999;
int A123, B123, C123;
void dfs(int cur, int par, vector<vector<int>>& adj123, vector<int>& depth, int dep){
depth[cur] = dep;
for (auto &e: adj123[cur]) if (e != par) dfs(e, cur, adj123, depth, dep + 1);
}
pair<int, int> diameter(){
vector<int> depth(10000, 0), depth2(10000, 0);
dfs(0, -1, adj123, depth, 0);
int max_depth = 0, end1, end2;
for (int i = 0; i < 10000; i++)
if (depth[i] > max_depth)
max_depth = depth[i], end1 = i;
max_depth = 0;
dfs(end1, -1, adj123, 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/pow5123[i];
v[i] = d;
num -= d * pow5123[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 * pow5123[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;
}
pair<int, int> decode12(int x){
return m[x];
}
void pre(){
pow5123.resize(12, 1);
for (int i = 1; i < 12; i++) pow5123[i] = pow5123[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});
}
}
adj123.resize(10000, vector<int>());
}
void one(int x, int y){
if (d1 == x && d2 == y) C123 = 0;
else if (d1 == x) C123 = 1;
else C123 = 2;
}
void rone(int x, int y){
if (C123 == 0) d1 = x, d2 = y;
else if (C123 == 1) d1 = x, d2 = c123;
else d1 = y, d2 = c123;
}
void two(int x, int y, int v){
if (d2 != c123){
if (Q123(x,v)) C123 = 0;
if (Q123(y,v)) C123 = 1;
} else {
if (d1 == x) C123 = 2;
if (d1 == y) C123 = 3;
if (d1 == v) C123 = 4;
}
}
void rtwo(int x, int y, int v){
if (C123 == 0) d1 = min(x, v), d2 = max(x, v);
if (C123 == 1) d1 = min(y, v), d2 = max(y, v);
if (C123 == 2) d1 = x, d2 = c123;
if (C123 == 3) d1 = y, d2 = c123;
if (C123 == 4) d1 = v, d2 = c123;
}
// 9982: 0, 9981
// 12: 9982, 9993
// 3: 9994, 9996
// 3: 9997, 9999
// x,y: 0 <= x < y <= 9981
// V = 9999*x + y
// V % 9999: y
// (V - y)/9999: x
int send_message(int N, int i, int Pi) {
if (i == 1) pre();
if (i <= 9981){
upd;
return 0;
}
if (i <= 9993){
if (c1 == -1){
auto [u, v] = diameter();
c1 = u, c2 = v;
}
upd;
int V = 9999*c1 + c2;
vector<int> enc = encode(V, 12);
return enc[i - 9982];
}
if (i <= 9996){
if (d1 == -1){
auto [u, v] = diameter();
d1 = u, d2 = v;
}
upd;
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 == a123) {
upd;
auto [u, v] = diameter();
if (P123(c1, c2) || P123(c1, p123) || P123(c1, q123)) A123 = 0;
if (P123(c1, r123) || P123(c1, a123) || P123(c2, p123)) A123 = 1;
if (P123(c2, q123) || P123(c2, r123) || P123(c2, a123)) A123 = 2;
if (P123(p123, q123) || P123(p123, r123) || P123(p123, a123)) A123 = 3;
if (P123(q123, r123) || P123(q123, a123) || P123(r123, a123)) A123 = 4;
return A123;
}
if (i == b123) {
upd;
auto [u, v] = diameter();
if (A123 == 0){
if (P123(c1, c2)) B123 = 0;
if (P123(c1, p123)) B123 = 1;
if (P123(c1, q123)) B123 = 2;
if (P123(c1, b123) || P123(c2, b123)) B123 = 3;
if (P123(p123, b123) || P123(q123, b123)) B123 = 4;}
if (A123 == 1){
if (P123(c1, r123)) B123 = 0;
if (P123(c1, a123) || P123(c1, b123)) B123 = 1;
if (P123(c2, p123)) B123 = 2;
if (P123(c2, b123) || P123(r123, b123)) B123 = 3;
if (P123(p123, b123) || P123(a123, b123)) B123 = 4;}
if (A123 == 2){
if (P123(c2, q123)) B123 = 0;
if (P123(c2, r123)) B123 = 1;
if (P123(c2, a123)) B123 = 2;
if (P123(c2, b123) || P123(q123, b123)) B123 = 3;
if (P123(r123, b123) || P123(a123, b123)) B123 = 4;}
if (A123 == 3){
if (P123(p123, q123)) B123 = 0;
if (P123(p123, r123)) B123 = 1;
if (P123(p123, a123)) B123 = 2;
if (P123(p123, b123) || P123(q123, b123)) B123 = 3;
if (P123(r123, b123) || P123(a123, b123)) B123 = 4;}
if (A123 == 4){
if (P123(q123, r123)) B123 = 0;
if (P123(q123, a123)) B123 = 1;
if (P123(r123, a123)) B123 = 2;
if (P123(q123, b123)) B123 = 3;
if (P123(r123, b123) || P123(a123, b123)) B123 = 4;}
d1 = u, d2 = v;
return B123;
}
upd;
int u = d1, v = d2; // u, v are before C123
tie(d1, d2) = diameter();
if (A123 == 0){
if (P123(c1, c2)) one(c1, c2);
if (P123(c1, p123)) one(c1, p123);
if (P123(c1, q123)) one(c1, q123);
if (P123(c1, b123) || P123(c2, b123)) two(c1, c2, b123);
if (P123(p123, b123) || P123(q123, b123)) two(p123, q123, b123);}
if (A123 == 1){
if (P123(c1, r123)) one(c1, r123);
if (P123(c1, a123) || P123(c1, b123)) two(a123, b123, c1);
if (P123(c2, p123)) one(c2, p123);
if (P123(c2, b123) || P123(r123, b123)) two(c2, r123, b123);
if (P123(p123, b123) || P123(a123, b123)) two(p123, a123, b123);}
if (A123 == 2){
if (P123(c2, q123)) one(c2, q123);
if (P123(c2, r123)) one(c2, r123);
if (P123(c2, a123)) one(c2, a123);
if (P123(c2, b123) || P123(q123, b123)) two(c2, q123, b123);
if (P123(r123, b123) || P123(a123, b123)) two(r123, a123, b123);}
if (A123 == 3){
if (P123(p123, q123)) one(p123, q123);
if (P123(p123, r123)) one(p123, r123);
if (P123(p123, a123)) one(p123, a123);
if (P123(p123, b123) || P123(q123, b123)) two(p123, q123, b123);
if (P123(r123, b123) || P123(a123, b123)) two(r123, a123, b123);}
if (A123 == 4){
if (P123(q123, r123)) one(q123, r123);
if (P123(q123, a123)) one(q123, a123);
if (P123(r123, a123)) one(r123, a123);
if (P123(q123, b123)) one(q123, b123);
if (P123(r123, b123) || P123(a123, b123)) two(r123, a123, b123);}
return C123;
}
pair<int, int> longest_path(vector<int> S) {
vector<int> part1(12);
for (int i = 9982; i <= 9993; i++) part1[i - 9982] = S[i];
int V = decode(part1);
int c1 = (V - V%c123)/c123, c2 = V%c123;
vector<int> part2(3);
for (int i = p123; i <= r123; i++) part2[i - p123] = S[i];
V = decode(part2);
if (V <= 67){
auto [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);
}
A123 = S[a123], B123 = S[b123], C123 = S[c123];
if (A123 == 0){
if (B123 == 0) rone(c1, c2);
if (B123 == 1) rone(c1, p123);
if (B123 == 2) rone(c1, q123);
if (B123 == 3) rtwo(c1, c2, b123);
if (B123 == 4) rtwo(p123, q123, b123);}
if (A123 == 1){
if (B123 == 0) rone(c1, r123);
if (B123 == 1) rtwo(a123, b123, c1);
if (B123 == 2) rone(c2, p123);
if (B123 == 3) rtwo(c2, r123, b123);
if (B123 == 4) rtwo(p123, a123, b123);}
if (A123 == 2){
if (B123 == 0) rone(c2, q123);
if (B123 == 1) rone(c2, r123);
if (B123 == 2) rone(c2, a123);
if (B123 == 3) rtwo(c2, q123, b123);
if (B123 == 4) rtwo(r123, a123, b123);}
if (A123 == 3){
if (B123 == 0) rone(p123, q123);
if (B123 == 1) rone(p123, r123);
if (B123 == 2) rone(p123, a123);
if (B123 == 3) rtwo(p123, q123, b123);
if (B123 == 4) rtwo(r123, a123, b123);}
if (A123 == 4){
if (B123 == 0) rone(q123, r123);
if (B123 == 1) rone(q123, a123);
if (B123 == 2) rone(r123, a123);
if (B123 == 3) rone(q123, b123);
if (B123 == 4) rtwo(r123, a123, b123);}
return {d1, d2};
}
