#include "migrations.h"
#include "bits/stdc++.h"
using namespace std;
vector<int>G[20001];
pair<int,int> mx_dis;
int md[20001];
void dfs(int v,int p,int cur_dis){
mx_dis=max(mx_dis,{cur_dis,v});
for(int u:G[v]){
if(u==p) continue;
dfs(u,v,cur_dis+1);
}
}
int send_message(int N,int i,int Pi)
{
G[i].push_back(Pi);
G[Pi].push_back(i);
if(i!=N-1){
mx_dis={0,i};
dfs(i,-1,0);
md[i]=mx_dis.first;
return mx_dis.second;
}
else{
mx_dis={0,i};
dfs(i,-1,0);
md[i]=mx_dis.first;
int cur_mx=0;
for(int i=1;i<N;i++) cur_mx=max(cur_mx,md[i]);
for(int i=1;i<N;i++){
if(cur_mx==md[i]&&i!=N-1) return i;
else if(cur_mx==md[i]&&i==N-1) return mx_dis.second+10000;
}
return 0;
}
}
pair<int,int>longest_path(vector<int>S)
{
S[0]=0;
int n=S.size();
if(S[n-1]<10000) return {S[n-1],S[S[n-1]]};
else return {n-1,S[n-1]-10000};
}
