#include <bits/stdc++.h>
using namespace std;
using ll = long long;
constexpr int MAXN = 10000 + 5;
constexpr int LOG = 14; // 2^14 > 10000
/* -------- lưu giữa các lần gọi -------- */
namespace {
int Nglob = 0;
int depth_[MAXN];
int up[LOG][MAXN];
int A = 0, B = 0, D = 0; // hai đầu đường kính tạm
int lastSentD = 0; // D của lần gửi gần nhất (0 = chưa)
int messagesSent = 0;
}
/* ---------- hàm tiện ---------- */
int climb(int v, int k) {
for (int b = 0; k; ++b, k >>= 1)
if (k & 1) v = up[b][v];
return v;
}
int lca(int u, int v) {
if (depth_[u] < depth_[v]) swap(u, v);
u = climb(u, depth_[u] - depth_[v]);
if (u == v) return u;
for (int b = LOG - 1; b >= 0; --b)
if (up[b][u] != up[b][v]) {
u = up[b][u];
v = up[b][v];
}
return up[0][u];
}
inline int dist(int u, int v) {
int w = lca(u, v);
return depth_[u] + depth_[v] - 2 * depth_[w];
}
/* ===========================================================
========== 1. HÀM ĐOÀN KHẢO SÁT ======================== */
int send_message(int N, int i, int Pi) {
if (i == 1) { // khởi tạo lần đầu
Nglob = N;
depth_[0] = 0;
for (int b = 0; b < LOG; ++b) up[b][0] = 0;
}
/* -- cập nhật bảng tổ tiên cho đỉnh i -- */
depth_[i] = depth_[Pi] + 1;
up[0][i] = Pi;
for (int b = 1; b < LOG; ++b)
up[b][i] = up[b - 1][ up[b - 1][i] ];
/* -- kiểm tra đường kính -- */
if (i == 1) { // bước đầu: A=0, B=1
A = 0; B = 1; D = 1;
} else {
int d1 = dist(i, A);
int d2 = dist(i, B);
if (d1 >= d2 && d1 > D) { B = i; D = d1; }
else if (d2 > d1 && d2 > D) { A = i; D = d2; }
}
/* -- quyết định có gửi hay không -- */
bool send = false;
int remainingNodes = Nglob - 1 - i;
int remainingBudget = 50 - messagesSent;
if (lastSentD == 0) send = true;
else if (D >= 2 * lastSentD) send = true;
else if (remainingNodes <= remainingBudget - 1) send = true;
if (!send) return 0; // không gửi
int other = (A == i ? B : A);
++messagesSent;
lastSentD = D;
return other + 1; // 1 … 10000
}
/* ===========================================================
========== 2. HÀM BẢO TÀNG ============================== */
std::pair<int,int> longest_path(std::vector<int> S) {
for (int i = (int)S.size() - 1; i >= 1; --i)
if (S[i] > 0) // thông điệp cuối
return {i, S[i] - 1};
return {0,0}; // N = 1
}
