#include <bits/stdc++.h>
using namespace std;
vector <int> v[10005];
int ans;
int T[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};
int send_message(int N, int i, int Pi){
if (i<9991){
v[i].push_back(Pi);
v[Pi].push_back(i);
return 0;
}
else if(i>=9991 && i<=9996){
int j=9996-i;
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,i+1);
T[i]=p.first;J[i]=p.second;
return (T[9991]%mod5[j]/div5[j]);
}
else if(i==9997){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,9998);
T[9997]=p.first;J[9997]=p.second;ans=0;
for (int j=9991; j<=9997; j++)if(J[j]>=J[9996]){ans=j-9991;break;}
return(ans/5);
}
else if(i==9998){
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N-1);
T[9998]=p.first;J[9998]=p.second;
return(ans%5);
}
else{
v[i].push_back(Pi);v[Pi].push_back(i);
pair <int,int> p;p=bfs(0,N);
T[9999]=p.first;J[9999]=p.second;
if (J[9997]>=J[9999]){ans=0;}
else if (J[9998]>=J[9999]){ans=1;}
else{ans=2;}
return (ans);
}
}
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=0;
//return {0,S.size()-2};
for (int i=10000-9; i<10000-3; i++){
pos_ans+=S[i]*intPow(5,10000-4-i);
}
if (S[10000-3]==1){
pos_ans=10000-3;
if (S[10000-2]==0){pos_ans=10000-4;}
}
else if(S[10000-2]!=0){
pos_ans=10000-9+S[10000-2];
}
if (S[10000-1]==2){
pos_ans=10000-1;
// return {-S[10000-1],-S[10000-2]};
}
if (S[10000-1]==1){
pos_ans=10000-2;
}
return {0,pos_ans};
}
