#include <bits/stdc++.h>
using namespace std;
vector <int> v[20001];
int T1,J1,T2,J2;
pair<int,int> bfs(int node, int mx){
int n=mx;
vector<int> dist(n, -1);
queue<int> q;
dist[node]=0;
q.push(node);
int f=node;
while (!q.empty()) {
int t=q.front();
q.pop();
for (int i=0; i<v[t].size(); i++) {
int to=v[t][i];
if (dist[to]==-1) {
dist[to]=dist[t]+1;
q.push(to);
if (dist[to]>dist[f])
f=to;
}}}
return {f,dist[f]};
}
int send_message(int N, int i, int Pi){
if (i<N-3){
v[i].push_back(Pi);
v[Pi].push_back(i);
return 0;
}
else if(i==N-3){
v[i].push_back(Pi);
v[Pi].push_back(i);
pair <int,int> p;
p=bfs(0,N-2);
T1=p.first;
J1=p.second;
return (T1/101);
}
else if(i==N-2){
v[i].push_back(Pi);
v[Pi].push_back(i);
pair <int,int> p;
p=bfs(0,N-1);
T2=p.first;
J2=p.second;
return (T1%101);
}
else{
pair<int,int> p;
//int len=J2;
v[i].push_back(Pi);
v[Pi].push_back(i);
p=bfs(0,N);
T1=p.second;
if (J1>=T1){
return 0;
}
else if(J2>=T1){
return 1;
}
else{
return 2;
}
}
}
std::pair<int,int> longest_path(std::vector<int> S){
if (S[S.size()-1]==0){
return {0,S[S.size()-3]*101+S[S.size()-2]};
}
else if (S[S.size()-1]==1){
return {0,S.size()-2};
}
else if (S[S.size()-1]==2){
return {0,S.size()-1};
}
else{
return {0,-1};
}
}
