#include <bits/stdc++.h>
using namespace std;
/* ---------- research team side ---------- */
static int storedN = -1; // current test case size
static vector<int> parent; // parent[i] = P[i]
static bool answered = false; // have we already sent the answer
static int answerNode = 0; // deepest node (to send)
/* Called N-1 times, in order i = 1 .. N-1 */
int send_message(int N, int i, int Pi) {
// first call of a new test case: initialise storage
if (storedN != N) {
storedN = N;
parent.assign(N, -1);
answered = false;
answerNode = 0;
}
parent[i] = Pi; // remember the edge
// we send a single message at the very last visited site
if (i == N - 1 && !answered) {
// compute depths (parent indices are always smaller)
vector<int> depth(N, 0);
for (int v = 1; v < N; ++v) {
depth[v] = depth[parent[v]] + 1;
}
int best = 0, maxDepth = 0;
for (int v = 0; v < N; ++v) {
if (depth[v] > maxDepth) {
maxDepth = depth[v];
best = v;
}
}
answerNode = best; // guaranteed best >= 1 by problem guarantee
answered = true;
// return the node index (1 .. 9999) as the message
return answerNode;
}
// otherwise no message
return 0;
}
/* ---------- Museum side ---------- */
pair<int,int> longest_path(vector<int> S) {
int best = 0;
for (int x : S) if (x != 0) best = x; // the only non‑zero value
// by construction best >= 1, and (0,best) is a longest pair
return {0, best};
}
