#include <bits/stdc++.h>
using namespace std;
int p[10001];
vector<vector<int>> a;
vector<int> v;
void dfs(int u, int k, int cnt){
v[u] = cnt;
for(int e : a[u]) if(e != k) dfs(e, u, cnt + 1);
}
int vt[7];
pair<int,int> ml = {-1,-1};
int send_message(int N, int i, int Pi){
p[i] = Pi;
if(i >= N - 2){
a.assign(N + 1, {}); v.assign(N + 1, 0);
for(int j = 0; j <= i; j++) {
a[p[j]].push_back(j);
a[j].push_back(p[j]);
}
dfs(0, -1, 0);int u = 0;
for(int j = 0; j <= i; j++) if(v[j] > v[u]) u = j;
v.assign(N + 1, 0);
dfs(u, -1, 0);int vtx = u;
for(int j = 0; j <= i; j++) if(v[j] > v[vtx]) vtx = j;
int x = u, y = vtx;if(x > y) swap(x, y); int kp = 0;
if(i == N - 1 && ml.first != -1 && make_pair(x, y) != ml) return 10000+x;
ml = make_pair(x,y);
if(i == N-2) return x;
return y;
}
return 0;
}
pair<int,int> longest_path(vector<int> S){
if(S.back() >= 10000)return {S.back()-10000, S.size()-1};
return {S[S.size()-2], S.back()};
}
