#include "migrations.h"
using namespace std;
vector<vector<int>> Tree;
int n;
vector<int> depth;
void init(){
Tree.clear();
Tree.resize(n);
depth.clear();
depth.resize(n);
depth[0]=0;
}
int ans=0;
int perAns=-1;
int send_message(int N, int i, int Pi) {
n=N;
if(i==1){
init();
}
Tree[Pi].push_back(i);
depth[i]=depth[Pi]+1;
if(depth[i]>depth[ans])ans=i;
if(i<n-11)return 0;
if(perAns==-1)perAns=ans;
if(i==n-3){
if(ans<n-11)return 1;
int t=n-3-ans;
if(ans==i)return 0;
if(t>=2)return 4;
return t+2;
}
if(i==n-2){
if(ans<n-11)return 1;
int t=n-3-ans;
if(ans==i)return 0;
if(t<=2)return 1;
t-=2;
return t+1;
}
if(i==n-1){
if(ans<n-11)return 1;
int t=n-3-ans;
if(ans==i)return 0;
if(t<=5)return 1;
t-=5;
return t+1;
}
int re=perAns%4;
perAns/=4;
return re;
}
pair<int, int> longest_path(vector<int> S) {
n=S.size();
if(S.back()==0)return {0,n-1};
if(S[n-2]==0)return {0,n-2};
if(S[n-3]==0)return {0,n-3};
if(S[n-3]==1){
int ans=0;
for(int i=n-4;i>=n-11;i--){
ans*=4;
ans+=S[i];
}
return {0,ans};
}
int ans=n-3;
ans-=S[n-3]-2;
ans-=S[n-2]-1;
ans-=S[n-1]-1;
return {0,ans};
}
