#include <bits/stdc++.h>
using namespace std;
vector <int> v[10005];
int ans;
int T[10005];
int K[10005];
int J[10005];
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 div5[6]={1,5,25,125,625,3125};
int mod5[6]={5,25,125,625,3125,15625};
//[A],A,A,A,A,A,X,X,X,X,X,X,[B],B,Y,Y,[C],Z,T
int send_message(int N, int i, int Pi){
if (i<9981){
v[i].push_back(Pi);
v[Pi].push_back(i);
return 0;
}
else if(i>=9981 && i<=9986){
int j=9986-i;
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
return (T[9981]%mod5[j]/div5[j]);
}
else if(i>=9987 && i<=9992){
int j=9992-i;
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
return (K[9981]%mod5[j]/div5[j]);
}
else if(i==9993){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
ans=0;
if (T[9993]<=9981){ans=0;}
else{ans=T[9993]-9981;}
return(ans/5);
}
else if(i==9994){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
return(ans%5);
}
else if(i==9995){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
ans=0;
if (K[9993]<=9981){ans=0;}
else{ans=K[9993]-9981;}
return(ans/5);
}
else if(i==9996){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
return(ans%5);
}
else if(i==9997){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
ans=0;
if (T[9997]<=9993){ans=0;}
else{ans=T[9997]-9993;}
return ans;
}
else if(i==9998){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
ans=0;
if (K[9997]<=9993){ans=0;}
else{ans=K[9997]-9993;}
return ans;
}
else{
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p1,p2,p3,p4;
p1=bfs(0,i+1);p2=bfs(p1.first,i+1);
J[i]=p2.second;
if (J[i]>J[i-1]){T[i]=p1.first;K[i]=p2.first;}
else{
p3=bfs(T[i-1],i+1);
p4=bfs(K[i-1],i+1);
if (p3.second==p2.second){T[i]=T[i-1];K[i]=p3.first;}
else{T[i]=p4.first;K[i]=K[i-1];}
}
if (K[9999]<=9997 && T[9999]<=9997){
return 0;
}
else if(T[9999]=9998){
return 1;
}
else if(T[9999]=9999){
return 2;
}
else if(K[9999]=9999){
return 3;
}
else{
return 4;
}
}
}
long long intPow(long long base, long long exp1) {
long long result = 1;
while (exp1--) result *= base;
return result;
}
std::pair<int,int> longest_path(std::vector<int> S){
int pos_ans_x=0;
int pos_ans_y=0;
for (int i=9981; i<9987; i++){
pos_ans_x+=S[i]*intPow(5,9986-i);
}
for (int i=9987; i<9993; i++){
pos_ans_x+=S[i]*intPow(5,9992-i);
}
int nm_x=0;
int nm_y=0;
nm_x=S[9993]*5+S[9994];
nm_y=S[9995]*5+S[9996];
if (nm_x!=0){
pos_ans_x=9981+nm_x;
}
if (nm_y!=0){
pos_ans_y=9981+nm_y;
}
nm_x=S[9997];
nm_y=S[9998];
if (nm_x!=0){
pos_ans_x=9993+nm_x;
}
if (nm_y!=0){
pos_ans_y=9993+nm_y;
}
if (S[9999]==4){
pos_ans_x=9998;
pos_ans_y=9999;
}
if (S[9999]==3){
pos_ans_y=9999;
}
if (S[9999]==2){
pos_ans_x=9999;
}
if (S[9999]==1){
pos_ans_x=9998;
}
return {pos_ans_x,pos_ans_y};
}
