#include "migrations.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int maxn = 1e4 + 10;
int n;
vector < int > g[maxn];
int mxdist, mx;
void dfs(int beg, int from, int dist)
{
if(dist > mxdist)
{
mx = beg;
mxdist = dist;
}
for (auto nb: g[beg])
{
if(nb == from)continue;
dfs(nb, beg, dist+1);
}
}
int mx2, mxdist2 = 0;
void dfs2(int beg, int from, int dist)
{
if(dist > mxdist2)
{
mx2 = beg;
mxdist2 = dist;
}
for (auto nb: g[beg])
{
if(nb == from)continue;
dfs2(nb, beg, dist+1);
}
}
int send_message(int N, int i, int Pi)
{
n = N;
g[Pi].pb(i);
g[i].pb(Pi);
if(i == n-2)
{
mxdist = 0;
mx = 0;
dfs(0, -1, 0);
return mx + 1;
}
else if(i == n-1)
{
mxdist2 = 0;
mx2 = 0;
dfs2(n-1, -1, 0);
if(mxdist2 > mxdist)
{
return n + mx2;
}
else
{
int a = mx;
mxdist = 0;
mx = 0;
dfs(a, -1, 0);
return mx + 1;
}
}
else return 0;
}
std::pair<int, int> longest_path(std::vector<int> S)
{
n = S.size();
std::pair < int, int > p;
if(S[n-1] >= n)
{
p.first = S[n-1] - n;
p.second = n-1;
}
else
{
p.first = S[n-2]-1;
p.second = S[n-1]-1;
}
return p;
}
