#include <bits/stdc++.h>
using namespace std;
/* -------------------------------------------------------------
Global data – survives the whole first run
------------------------------------------------------------ */
static int N_global = -1; // number of sites, set at first call
static vector<int> parent_vec; // parent[i] = Pi
static int answer_u = -1, answer_v = -1; // diameter ends
static const string FILE_NAME = "answer.txt";
/* -------------------------------------------------------------
Helper: find farthest vertex and distances (BFS)
------------------------------------------------------------ */
static pair<int, vector<int>> bfs_farthest(int start,
const vector<vector<int>>& adj)
{
int n = (int)adj.size();
vector<int> dist(n, -1);
queue<int> q;
dist[start] = 0;
q.push(start);
int far = start;
while (!q.empty()) {
int v = q.front(); q.pop();
for (int to : adj[v]) {
if (dist[to] == -1) {
dist[to] = dist[v] + 1;
q.push(to);
if (dist[to] > dist[far]) far = to;
}
}
}
return {far, move(dist)};
}
/* -------------------------------------------------------------
The function called while the team visits the sites
------------------------------------------------------------ */
int send_message(int N, int i, int Pi)
{
// first call – initialise structures
if (N_global == -1) {
N_global = N;
parent_vec.assign(N, -1); // parent[0] stays -1
}
// store the parent of site i
parent_vec[i] = Pi;
// after the last site we know the whole tree
if (i == N - 1) {
// build adjacency list
vector<vector<int>> adj(N);
for (int v = 1; v < N; ++v) {
int p = parent_vec[v];
adj[v].push_back(p);
adj[p].push_back(v);
}
// two BFS to obtain a diameter
auto first = bfs_farthest(0, adj);
int a = first.first;
auto second = bfs_farthest(a, adj);
int b = second.first;
answer_u = a;
answer_v = b;
// write the answer to a temporary file for the second run
ofstream ofs(FILE_NAME, ios::out | ios::trunc);
if (ofs) {
ofs << answer_u << ' ' << answer_v << '\n';
ofs.close();
}
}
// we do not need to send any message
return 0; // S[i] = 0 → no message
}
/* -------------------------------------------------------------
The function called after all messages have been collected
------------------------------------------------------------ */
pair<int,int> longest_path(vector<int> S)
{
// read the answer from the file written after the last call
ifstream ifs(FILE_NAME);
int u = 0, v = 0;
if (ifs) {
ifs >> u >> v;
ifs.close();
return {u, v};
}
// fallback – should never happen in correct runs
return {0, 0};
}
