#include <bits/stdc++.h>
using namespace std;
vector <int> v[20001];
int T8,J8,T7,J7,T6,J6,T5,J5,T4,J4,T3,J3,T2,J2,T1,J1,ans;
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-8){
v[i].push_back(Pi);
v[Pi].push_back(i);
return 0;
}
else if(i==N-8){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-8);
T8=p.first;J8=p.second;
return (T8/(5*5*5*5*5));
}
else if(i==N-7){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-7);
T7=p.first;J7=p.second;
return (T8%(5*5*5*5*5)/(5*5*5*5));
}
else if(i==N-6){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-6);
T6=p.first;J6=p.second;
return (T8%(5*5*5*5*5)%(5*5*5*5)/(5*5*5));
}
else if(i==N-5){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-5);
T5=p.first;J5=p.second;
return (T8%(5*5*5*5*5)%(5*5*5*5)%(5*5*5)/(5*5));
}
else if(i==N-4){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-4);
T4=p.first;J4=p.second;
return (T8%(5*5*5*5*5)%(5*5*5*5)%(5*5*5)%(5*5)/(5));
}
else if(i==N-3){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-3);
T3=p.first;J3=p.second;
ans=0;
if (J8>=J3){ans=0;}
else if (J7>=J3){ans=1;}
else if (J6>=J3){ans=2;}
else if (J5>=J3){ans=3;}
else if (J4>=J3){ans=4;}
else{ans=5;}
return(ans/5);
}
else if(i==N-2){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-2);
T2=p.first;J2=p.second;
return(ans%5);
}
else{
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-1);
T1=p.first;J1=p.second;
if (J3>=J1){ans=0;}
else if (J2>=J1){ans=1;}
else{ans=2;}
return (ans);
}
}
long long intPow(long long base, long long exp) {
long long result = 1;
while (exp--) result *= base;
return result;
}
std::pair<int,int> longest_path(std::vector<int> S){
int pos_ans=0;
return {0,S.size()-1};
for (int i=10000-8; i<10000-3; i++){
pos_ans+=S[i]*intPow(5,10000-4-i);
}
if (S[10000-3]==1){pos_ans=10000-3;}
else if(S[10000-2]!=0){
pos_ans=10000-8+S[10000-2];
}
if (S[10000-1]==2){
pos_ans=10000-1;
}
if (S[10000-1]==1){
pos_ans=10000-2;
}
return {0,pos_ans};
}
