#include <bits/stdc++.h>
using namespace std;
/* send_message:
called N-1 times, in order i = 1 .. N-1.
Must return 0 (no message) or an integer 1..20000.
At most 50 non‑zero returns are allowed.
*/
int send_message(int N, int i, int Pi) {
// static data that persists between calls
static bool initialized = false;
static int totalN = 0;
static vector<int> depth;
static int bestDepth = -1;
static int bestNode = -1; // deepest vertex seen so far
if (!initialized) {
// first call – allocate structures
totalN = N;
depth.assign(N, -1);
depth[0] = 0; // root
bestDepth = 0;
bestNode = 0;
initialized = true;
}
// compute depth of current vertex i
depth[i] = depth[Pi] + 1;
// update deepest vertex if needed
if (depth[i] > bestDepth) {
bestDepth = depth[i];
bestNode = i;
}
// send a message only at the last vertex
if (i == totalN - 1) {
// deepest vertex is always >0 when N>1
if (bestNode == 0) return 0; // N == 1 case (should not happen)
return bestNode; // 1 .. 9999 (< 20000)
}
// otherwise, send nothing
return 0;
}
/* longest_path:
receives the whole array S (size N, S[0]=0), where S[i] is the value
returned by send_message at site i.
Must return a pair of vertices forming a diameter.
*/
pair<int,int> longest_path(vector<int> S) {
int deepest = -1;
for (size_t i = 0; i < S.size(); ++i) {
if (S[i] != 0) deepest = S[i];
}
if (deepest == -1) {
// N == 1 : only vertex 0 exists
return {0, 0};
}
// By the problem promise, (0, deepest) is a correct diameter pair
return {0, deepest};
}
