#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
/* ------- Global data for the first run ------- */
static int Nglob = -1; // number of sites
static int LOG = 0; // log2(N)
static vector<int> depth; // depth of each node
static vector<array<int,15>> up; // binary lifting table (LOG ≤ 15 for N≤10000)
static int a_node = 0, b_node = 0; // current diameter ends
static int diam_len = 0; // current diameter length
static int start_idx = 0; // first index from which we start sending messages
static bool dummy_a_sent = false; // have we already sent the dummy for 'a' ?
static bool dummy_b_sent = false; // have we already sent the dummy for 'b' ?
/* ------- Helper functions ------- */
static inline int encode(int nodeIdx, int side) {
// side = 1 (a) or 2 (b)
// value is always in [1,20000] because nodeIdx ≤ 9999
return nodeIdx * 2 + side;
}
static inline int lca(int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
int diff = depth[u] - depth[v];
for (int k = LOG - 1; k >= 0; --k) {
if (diff & (1 << k)) u = up[u][k];
}
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k) {
if (up[u][k] != -1 && up[u][k] != up[v][k]) {
u = up[u][k];
v = up[v][k];
}
}
return up[u][0];
}
static inline int dist(int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
}
/* ------- The team procedure ------- */
int send_message(int N, int i, int Pi) {
// first call: initialise everything
if (Nglob == -1) {
Nglob = N;
LOG = 0;
while ((1 << LOG) <= N) ++LOG; // LOG ≤ 15 for N = 10000
depth.assign(N, 0);
up.assign(N, array<int,15>{});
for (int k = 0; k < LOG; ++k) up[0][k] = -1;
a_node = b_node = 0;
diam_len = 0;
dummy_a_sent = dummy_b_sent = false;
start_idx = max(1, N - 50); // we have at most 50 nodes at the end
}
/* store parent and fill binary lifting table */
up[i][0] = Pi;
depth[i] = depth[Pi] + 1;
for (int k = 1; k < LOG; ++k) {
int p = up[i][k - 1];
up[i][k] = (p == -1) ? -1 : up[p][k - 1];
}
/* update the current diameter */
int side = 0; // 0 = no change, 1 = a becomes i, 2 = b becomes i
int new_diam = diam_len;
int da = dist(i, a_node);
int db = dist(i, b_node);
if (da > new_diam) {
new_diam = da;
side = 2; // b becomes i
} else if (db > new_diam) {
new_diam = db;
side = 1; // a becomes i
}
if (side == 1) a_node = i;
else if (side == 2) b_node = i;
diam_len = new_diam;
/* decide what to send */
if (i < start_idx) return 0; // we send nothing before the tail
int msg = 0;
if (i == start_idx) {
// first node of the tail: dummy message that tells the current value of a
msg = encode(a_node, 1);
dummy_a_sent = true;
// we deliberately ignore a possible side update here; a will be reported later if it changes again
} else {
if (!dummy_b_sent) {
if (side == 0) {
// we have a quiet step – perfect moment to emit dummy for b
msg = encode(b_node, 2);
dummy_b_sent = true;
} else if (i == Nglob - 2) {
// we are at the second‑last node and still have not emitted b.
// Sacrifice this node to send dummy b; a will still be updated later (at the last node)
msg = encode(b_node, 2);
dummy_b_sent = true;
// side update for a is ignored here.
} else {
// normal side update
msg = encode(i, side);
if (side == 1) dummy_a_sent = true;
else dummy_b_sent = true; // side == 2, we have now seen b change
}
} else {
// dummy for b already sent – just report side updates
if (side != 0) {
msg = encode(i, side);
if (side == 1) dummy_a_sent = true;
else dummy_b_sent = true;
} else {
msg = 0;
}
}
}
return msg;
}
/* ------- The museum procedure ------- */
std::pair<int,int> longest_path(std::vector<int> S) {
int a = 0, b = 0;
for (size_t i = 1; i < S.size(); ++i) {
int v = S[i];
if (v == 0) continue;
int side = (v % 2 == 0) ? 2 : 1; // even → side 2 (b), odd → side 1 (a)
int node = (v - side) / 2;
if (side == 1) a = node;
else b = node;
}
return {a, b};
}
