#include <bits/stdc++.h>
using namespace std;
/* -------------------------------------------------------------
Global state used by the team while processing the calls.
It is cleared automatically on each program run.
------------------------------------------------------------- */
static int N_global = 0;
static vector<int> depth; // depth[i] = distance from root 0
static int maxDepth = -1; // current maximal depth
static int maxNode = -1; // node achieving maxDepth
static bool initialized = false;
/* -------------------------------------------------------------
send_message
Called N‑1 times, with i = 1 … N‑1, Pi being the parent of i.
Returns 0 (no message) or a positive integer (the only message).
------------------------------------------------------------- */
int send_message(int N, int i, int Pi) {
if (!initialized) {
N_global = N;
depth.assign(N_global, 0); // depth[0] = 0 already
maxDepth = 0;
maxNode = 0;
initialized = true;
}
// compute depth of the current node
depth[i] = depth[Pi] + 1;
if (depth[i] > maxDepth) {
maxDepth = depth[i];
maxNode = i;
}
// send the answer only at the very last site
if (i == N_global - 1) {
// encode deepest node id + 1 (always 1 … 20000)
return maxNode + 1;
}
return 0; // no message
}
pair<int,int> longest_path(vector<int> S) {
int leaf = -1;
for (size_t i = 0; i < S.size(); ++i) {
if (S[i] != 0) { // there is exactly one such entry
leaf = S[i] - 1; // decode deepest node
}
}
if (leaf == -1) leaf = 0; // safety, should never happen
return {0, leaf};
}
