#include <bits/stdc++.h>
using namespace std;
static const int LOG = 15; // because 2^14 = 16384 > 10000
// --------------------------------------------------------------
// Global state (kept between many calls of send_message)
// --------------------------------------------------------------
static int N_glob = -1;
static vector<int> depth_;
static vector<array<int, LOG>> up;
static vector<int> parent_;
static int a_ = 0, b_ = 0; // current diameter ends
static int diam_len = 0; // length of current diameter
static int msg_cnt = 0; // how many messages have been sent
static bool stop_ = false; // after 50 messages we silence everything
static vector<int> S_store; // answer list
// --------------------------------------------------------------
static int lca(int u, int v) {
if (depth_[u] < depth_[v]) swap(u, v);
int diff = depth_[u] - depth_[v];
int bit = 0;
while (diff) {
if (diff & 1) u = up[u][bit];
diff >>= 1;
++bit;
}
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 int dist_uv(int u, int v) {
int w = lca(u, v);
return depth_[u] + depth_[v] - 2 * depth_[w];
}
// --------------------------------------------------------------
// Online part : send_message
// --------------------------------------------------------------
int send_message(int N, int i, int Pi) {
if (N_glob == -1) {
N_glob = N;
depth_.assign(N, 0);
up.assign(N, {});
for (int v = 0; v < N; ++v) up[v].fill(-1);
parent_.assign(N, -1);
a_ = b_ = 0;
diam_len = 0;
msg_cnt = 0;
stop_ = false;
S_store.assign(N, 0);
}
parent_[i] = Pi;
depth_[i] = depth_[Pi] + 1;
up[i][0] = Pi;
for (int k = 1; k < LOG; ++k) {
int anc = up[i][k - 1];
up[i][k] = (anc != -1 ? up[anc][k - 1] : -1);
}
int da = dist_uv(i, a_);
int db = dist_uv(i, b_);
bool updated = false;
int other = -1;
if (da > diam_len && da >= db) {
b_ = i;
diam_len = da;
other = a_;
updated = true;
} else if (db > diam_len) {
a_ = i;
diam_len = db;
other = b_;
updated = true;
}
if (!stop_ && msg_cnt < 50 && updated) {
S_store[i] = other + 1;
++msg_cnt;
} else {
S_store[i] = 0;
if (!updated) {
if (!stop_ && msg_cnt >= 50) {
stop_ = true;
}
}
}
return S_store[i];
}
// --------------------------------------------------------------
// Offline part : longest_path
// --------------------------------------------------------------
std::pair<int,int> longest_path(std::vector<int> S) {
int last_idx = -1;
for (int i = (int)S.size() - 1; i >= 0; --i) {
if (S[i] != 0) {
last_idx = i;
break;
}
}
if (last_idx == -1) {
return {0, 0};
}
int u = last_idx;
int v = S[u] - 1;
return {u, v};
}
