#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 10000;
int par[maxn];
int ret;
int mxdep;
void dfs(int st, vector<int>g[], int p, int dep){
if(dep>mxdep){
ret=st;
mxdep=dep;
}
for(int i : g[st]){
if(i==p)
continue;
dfs(i,g,st,dep+1);
}
}
int a,b;
int send_message(int n, int i, int Pi) {
par[i]=Pi;
if(i==n-2){
//must send a+b
vector<int>g[n];
for(int i = 1;i<n-1;i++){
g[i].push_back(par[i]);
g[par[i]].push_back(i);
}
mxdep=0;
dfs(0,g,-1,0);
a = ret;
mxdep=0;
dfs(a,g,-1,0);
b=ret;
if(a<b){
swap(a,b);
}
return a+b;
}
if(i==n-1){
//it is done.
vector<int>g[n];
for(int i = 1;i<n;i++){
g[i].push_back(par[i]);
g[par[i]].push_back(i);
}
int old = mxdep;
mxdep=0;
dfs(a,g,-1,0);
int mxdepa = mxdep;
int ca = ret;
mxdep=0;
dfs(b,g,-1,0);
int mxdepb = mxdep;
int cb = ret;
if(max({mxdepa,mxdepb,old})==old){
return a;
}
else if(mxdepa>old){
return a+10000;
}
else{
return b+10000;
}
}
return 0;
}
pair<int, int> longest_path(vector<int> S) {
int las2 = S[S.size()-2];
int las1 = S[S.size()-1];
if(las1>=10000){
return {las1-10000,9999};
}
else{
return {las2-las1,las1};
}
}
