#include <bits/stdc++.h>
#include "migrations.h"
using namespace std;
namespace {
const int MAXN = 10000 + 5;
const int LOG = 15;
// Internal labels are 1-based.
// Original site v corresponds to internal vertex v + 1.
const int B[7] = {0, 33, 9, 5, 3, 3, 0};
const int E[7] = {0, 9828, 9968, 9988, 9994, 9996, 9998};
const int F[5][5] = {
{0, 1, 4, 5, 6},
{1, 0, 7, 8, 6},
{2, 3, 8, 4, 5},
{6, 7, 2, 3, 8},
{8, 3, 4, 5, 7}
};
const int G[5][3] = {
{2, 0, 3},
{0, 4, 5},
{2, 5, 3},
{2, 1, 3},
{0, 5, 1}
};
int curN = -1;
int up[MAXN][LOG];
int depth_[MAXN];
int diaX, diaY, diaLen;
vector<int> candX, candY;
int bucketX[MAXN], bucketY[MAXN];
int codeState;
int point[10], point2[6];
bool same_edge(int a, int b, int c, int d) {
return min(a, b) == min(c, d) && max(a, b) == max(c, d);
}
void init_sender(int N) {
curN = N;
for (int i = 0; i <= N + 1; ++i) {
depth_[i] = 0;
bucketX[i] = bucketY[i] = 0;
for (int k = 0; k < LOG; ++k) up[i][k] = 1;
}
for (int k = 0; k < LOG; ++k) up[1][k] = 1;
diaX = diaY = 1;
diaLen = 0;
candX.clear();
candY.clear();
codeState = 0;
}
int lca(int a, int b) {
if (depth_[a] < depth_[b]) swap(a, b);
int diff = depth_[a] - depth_[b];
for (int k = 0; k < LOG; ++k) {
if ((diff >> k) & 1) a = up[a][k];
}
if (a == b) return a;
for (int k = LOG - 1; k >= 0; --k) {
if (up[a][k] != up[b][k]) {
a = up[a][k];
b = up[b][k];
}
}
return up[a][0];
}
int dist_tree(int a, int b) {
int c = lca(a, b);
return depth_[a] + depth_[b] - 2 * depth_[c];
}
void update_diameter(int z) {
int dx = dist_tree(diaX, z);
int dy = dist_tree(z, diaY);
diaLen = max({diaLen, dx, dy});
// Ties are allowed. We only need any valid diameter.
if (diaLen == dx) {
diaY = z;
} else if (diaLen == dy) {
diaX = z;
}
}
void shrink_to_actual_buckets() {
vector<int> nx, ny;
for (int v : candX) {
if (bucketX[v] == bucketX[diaX]) nx.push_back(v);
}
for (int v : candY) {
if (bucketY[v] == bucketY[diaY]) ny.push_back(v);
}
candX.swap(nx);
candY.swap(ny);
}
void add_block_and_partition(int b) {
for (int v = E[b - 1] + 1; v <= E[b]; ++v) {
candX.push_back(v);
candY.push_back(v);
update_diameter(v);
}
int sx = (int)candX.size();
int sy = (int)candY.size();
int px = 0, py = 0;
for (int c = 0; c < B[b]; ++c) {
int tx = px + sx / B[b] + (c < sx % B[b]);
while (px < tx) {
bucketX[candX[px++]] = c;
}
int ty = py + sy / B[b] + (c < sy % B[b]);
while (py < ty) {
bucketY[candY[py++]] = c;
}
}
if (b == 1) {
// First block encodes an unordered bucket pair.
if (diaX < diaY) swap(diaX, diaY);
codeState = bucketX[diaX] * (bucketX[diaX] + 1) / 2 + bucketY[diaY];
} else {
codeState = bucketX[diaX] * B[b] + bucketY[diaY];
}
}
}
int send_message(int N, int i, int Pi) {
if (i == 1 || curN != N) init_sender(N);
int u = i + 1;
int p = Pi + 1;
depth_[u] = depth_[p] + 1;
up[u][0] = p;
for (int k = 1; k < LOG; ++k) {
up[u][k] = up[up[u][k - 1]][k - 1];
}
for (int b = 1; b <= 5; ++b) {
if (u == E[b + 1]) {
shrink_to_actual_buckets();
}
if (u == E[b]) {
add_block_and_partition(b);
}
if (E[b] <= u && u < E[b + 1]) {
if (codeState != 0 && (codeState - 1) / 4 == u - E[b]) {
return (codeState - 1) % 4 + 1;
}
}
}
// Last three special transmissions.
if (u == N - 2) {
candX.push_back(u - 1);
candX.resize(4, u);
candY.push_back(u - 1);
candY.resize(4, u);
update_diameter(u - 1);
update_diameter(u);
for (int t = 0; t < 4; ++t) {
point[t] = candX[t];
point[t + 4] = candY[t];
}
point[8] = u;
for (int c = 0; c < 5; ++c) {
for (int a = 0; a < 2; ++a) {
for (int b = 2; b < 5; ++b) {
if (a == 0 || b < 4) {
if (same_edge(diaX, diaY, point[F[c][a]], point[F[c][b]])) {
codeState = c;
return c;
}
}
}
}
}
}
if (u == N - 1) {
update_diameter(u);
point2[5] = u;
for (int t = 0; t < 5; ++t) {
point2[t] = point[F[codeState][t]];
}
for (int c = 0; c < 5; ++c) {
for (int a = 0; a < 2; ++a) {
if (same_edge(diaX, diaY, point2[G[c][a]], point2[G[c][a + 1]])) {
codeState = c;
return c;
}
}
}
}
if (u == N) {
update_diameter(u);
point[3] = u;
for (int t = 0; t < 3; ++t) {
point[t] = point2[G[codeState][t]];
}
int k = 0;
for (int a = 0; a < 4; ++a) {
for (int b = a + 1; b < 4; ++b) {
if (a == 0 && b == 2) continue;
if (same_edge(diaX, diaY, point[a], point[b])) {
return k;
}
++k;
}
}
}
return 0;
}
pair<int,int> longest_path(vector<int> S) {
int N = (int)S.size();
vector<int> a(N + 1, 0);
for (int u = 1; u <= N; ++u) {
a[u] = S[u - 1];
}
vector<int> X, Y;
static int bx[MAXN], by[MAXN];
for (int b = 1; b <= 5; ++b) {
for (int v = E[b - 1] + 1; v <= E[b]; ++v) {
X.push_back(v);
Y.push_back(v);
}
int sx = (int)X.size();
int sy = (int)Y.size();
int px = 0, py = 0;
for (int c = 0; c < B[b]; ++c) {
int tx = px + sx / B[b] + (c < sx % B[b]);
while (px < tx) {
bx[X[px++]] = c;
}
int ty = py + sy / B[b] + (c < sy % B[b]);
while (py < ty) {
by[Y[py++]] = c;
}
}
int h = 0;
int hx = 0;
int hy = 0;
for (int u = E[b]; u < E[b + 1]; ++u) {
if (a[u] != 0) {
h = (u - E[b]) * 4 + a[u];
}
}
if (b == 1) {
for (int i = 0; i < B[b]; ++i) {
for (int j = 0; j <= i; ++j) {
if (i * (i + 1) / 2 + j == h) {
hx = i;
hy = j;
}
}
}
} else {
hx = h / B[b];
hy = h % B[b];
}
vector<int> nX, nY;
for (int v : X) {
if (bx[v] == hx) nX.push_back(v);
}
for (int v : Y) {
if (by[v] == hy) nY.push_back(v);
}
X.swap(nX);
Y.swap(nY);
}
X.push_back(N - 3);
X.resize(4, N - 2);
Y.push_back(N - 3);
Y.resize(4, N - 2);
int p[9], q[6], r[4];
for (int t = 0; t < 4; ++t) {
p[t] = X[t];
p[t + 4] = Y[t];
}
p[8] = N - 2;
q[5] = N - 1;
for (int t = 0; t < 5; ++t) {
q[t] = p[F[a[N - 2]][t]];
}
r[3] = N;
for (int t = 0; t < 3; ++t) {
r[t] = q[G[a[N - 1]][t]];
}
int code = a[N];
int k = 0;
for (int i = 0; i < 4; ++i) {
for (int j = i + 1; j < 4; ++j) {
if (i == 0 && j == 2) continue;
if (k == code) {
return {r[i] - 1, r[j] - 1};
}
++k;
}
}
return {0, 0};
}
