#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
// ---------------------- Research team ----------------------
int send_message(int N, int i, int Pi) {
// Persistent state across calls in the FIRST run
static bool inited = false;
static int N_glob = 0, LOG = 0;
static vector<int> depth;
static vector<array<int, 15>> up; // 2^14 = 16384 > 10000
static int a = 0, b = 0, diam = 0; // current diameter endpoints and length
static int sent = 0; // messages sent (cap at 50)
if (!inited) {
inited = true;
N_glob = N;
LOG = 0;
while ((1 << LOG) <= max(1, N_glob)) ++LOG; // <= 14 for N<=10000
depth.assign(N_glob, 0);
up.assign(N_glob, array<int,15>{});
for (int k = 0; k < LOG; ++k) up[0][k] = 0;
a = b = 0;
diam = 0;
sent = 0;
}
// Update ancestry info for node i
depth[i] = depth[Pi] + 1;
up[i][0] = Pi;
for (int k = 1; k < LOG; ++k) up[i][k] = up[ up[i][k-1] ][k-1];
auto lift = [&](int u, int d) {
for (int k = 0; k < LOG; ++k) if (d & (1 << k)) u = up[u][k];
return u;
};
auto lca = [&](int u, int v) {
if (depth[u] < depth[v]) swap(u, v);
u = lift(u, depth[u] - depth[v]);
if (u == v) return u;
for (int k = LOG - 1; k >= 0; --k)
if (up[u][k] != up[v][k]) { u = up[u][k]; v = up[v][k]; }
return up[u][0];
};
auto dist = [&](int u, int v) {
int w = lca(u, v);
return depth[u] + depth[v] - 2 * depth[w];
};
int ans = 0;
// Check if the new node extends the diameter
int du = dist(i, a);
int dv = dist(i, b);
if (du > diam || dv > diam) {
// New diameter is (i, other), where other is the farther of (a,b)
int other;
if (du > dv) { other = a; b = i; diam = du; }
else { other = b; a = i; diam = dv; }
// Send at most 50 messages, encode endpoint as other+1 in [1..N]
if (sent < 50) {
ans = other + 1; // 1..10000 ≤ 20000
++sent;
}
}
return ans; // 0 = no message
}
// ---------------------- Museum ----------------------
std::pair<int,int> longest_path(std::vector<int> S) {
// Find the last non-zero message; its index is one endpoint, the value-1 the other
for (int i = (int)S.size() - 1; i >= 1; --i) {
if (S[i] != 0) {
return { i, S[i] - 1 };
}
}
// Fallback: if no messages (should not happen), tree has only node 0 or trivial
return {0, 0};
}
