#include <bits/stdc++.h>
using namespace std;
int p[10001];
vector<vector<int>> a;
vector<int> v;
void dfs(int u, int k, int cnt){
v[u] = cnt;
for(int e : a[u]) if(e != k) dfs(e, u, cnt + 1);
}
int ml = 1, num = 10000; bool tr = false, t = false, op = false;
int send_message(int N, int i, int Pi) {
p[i] = Pi;
if(i >= N - 40){
if(op) return 3;
a.assign(N + 1, {}); v.assign(N + 1, 0);
for(int j = 1; j <= N; j++){a[p[j]].push_back(j);}
dfs(0, -1, 0); int mx = 1;
for(int j = 2; j <= N; j++) if(v[j] > v[mx]) mx = j;
if(i > N-40 and mx != ml){
op = true;
return 3;
} ml = mx;
int cnt = 0; if(tr) return 4; int num2 = num;
while(mx % 10 == num2 % 10){
mx /= 10; num2 /= 10; cnt++;
if(num2 == 1){
tr = true;
return 4;
}
}
if(!t){
t = true;
return cnt;
}
t = false;
if(mx % 10 - num2 % 10 >= 2){
num2 += pow<int>(10, cnt)*2;
return 3;
} else{
num2 += pow<int>(10, cnt)*(mx % 10 - num2 % 10);
return mx % 10 - num2 % 10;
}
}
return 0;
}
pair<int, int> longest_path(vector<int> S){
int nm = 10000;
for(int i = S.size()-40; i < S.size(); i++){
if(S[i] == 3) return {0, i};
if(S[i] == 4) continue;
if(i & 1) nm += pow<int>(10, S[i-1])*S[i];
}
return {0, nm-10000};
}
