#include "migrations.h"
#include <bits/stdc++.h>
#define int long long
#define all(a) begin(a), end(a)
using namespace std;
const int N = 10'000;
const int LGN = 20;
vector<int> G[N];
pair<int, int> dfs(int v, int pa = -1) {
int ud = v, d = -1;
for (int u : G[v]) {
if (u == pa) continue;
auto [ud2, d2] = dfs(u, v);
if (d2 > d) ud = ud2, d = d2;
}
return {ud, d + 1};
}
int encrypt(int N, int a, int b) {
assert(a < b);
int X = 0;
for (int i = 0; i < a; i++) X += N - 1 - i;
for (int i = a + 1; i < b; i++) X++;
return X;
}
pair<int, int> decrypt(int N, int X) {
int a = 0, b = 1;
while (X >= N - 1 - a) X -= N - 1 - a, ++a, b = a + 1;
while (X >= 1) --X, ++b;
return {a, b};
}
int msg[N];
vector<int> R {0};
vector<int> C {19, 7, 4}, P {12, 3, 2};
pair<int, int> diameter() {
auto [u, du] = dfs(0);
auto [v, d] = dfs(u);
if (u > v) swap(u, v);
int a = find(all(R), u) - R.begin();
int b = find(all(R), v) - R.begin();
return {a, b};
}
int J1, K1;
vector<vector<int>> M1 {
{0, 1, 2},
{2, 3, 4},
{4, 0, 2},
{2, 4, 1},
{1, 3, 0}
};
int _N;
int32_t send_message(int32_t N, int32_t i, int32_t Pi) {
_N = N;
for (int x = 0; x < C.size(); x++) {
int c = C[x], p = P[x];
if (i == N - c) {
auto [a, b] = diameter();
int X = encrypt(R.size(), a, b);
R = {R[a], R[b]};
for (int j = 0; j < p; j++) {
msg[N - c + j] = X % 5;
X /= 5;
}
}
}
if (i == N - 2) {
G[i].push_back(Pi);
G[Pi].push_back(i);
R.push_back(i);
auto [a, b] = diameter();
for (int j = 0; j < 5; j++) {
for (int k = 0; k < 2; k++) {
if (set<int>{a, b} == set<int>{M1[j][k], M1[j][k + 1]}) {
msg[N - 2] = j;
J1 = j; K1 = k;
}
}
}
} else if (i == N - 1) {
G[i].push_back(Pi);
G[Pi].push_back(i);
R.push_back(i);
auto [a, b] = diameter();
if (b == 5) {
for (int k = 0; k < 3; k++) {
if (M1[J1][k] == a) msg[N - 1] = 2 + k;
}
} else {
for (int k = 0; k < 2; k++) {
if (set<int>{a, b} == set<int>{M1[J1][k], M1[J1][k + 1]}) {
msg[N - 1] = k;
}
}
}
} else {
G[i].push_back(Pi);
G[Pi].push_back(i);
R.push_back(i);
}
return msg[i];
}
pair<int32_t, int32_t> longest_path(vector<int32_t> S) {
R = vector<int>{0};
int prv = 1;
for (int x = 0; x < C.size(); x++) {
int c = C[x], p = P[x];
while (prv < N - c) R.push_back(prv++);
int X = 0;
for (int i = (N - c) + p - 1; i >= (N - c); i--) {
X = X * 5 + S[i];
}
auto [a, b] = decrypt(R.size(), X);
R = {R[a], R[b]};
}
R.push_back(N - 4);
R.push_back(N - 3);
R.push_back(N - 2);
switch (S[N - 1]) {
case 0:
return {R[M1[S[N - 2]][0]], R[M1[S[N - 2]][1]]};
case 1:
return {R[M1[S[N - 2]][1]], R[M1[S[N - 2]][2]]};
case 2:
return {R[M1[S[N - 2]][0]], N - 1};
case 3:
return {R[M1[S[N - 2]][1]], N - 1};
case 4:
return {R[M1[S[N - 2]][2]], N - 1};
}
}
