#include <bits/stdc++.h>
#include "migrations.h"
using namespace std;
#define pb push_back
pair<int,int> ans={-1,-1},mx={-1,-1};
int di,lk=-1;
vector<int> adj[10005];
int e=0,rr=-1;
void dfs(int node,int par,int dist=0){
if(lk==-1 && mx.first<dist)mx={dist,node};
if(lk!=-1 && node==lk && dist>di)e=dist;
for(auto i:adj[node]){
if(i==par)continue;
dfs(i,node,dist+1);
}
}
int send_message(int N, int i, int Pi) {
if(i>=9979 && i<9993){
if(i==9979){
dfs(0,-1);
int x=mx.second;
rr=x;
mx={-1,-1};
dfs(x,-1);
ans={x,mx.second};
di=mx.first;
rr=-1;
}
adj[i].pb(Pi);
adj[Pi].pb(i);
e=0; lk=ans.second;
dfs(i,-1);
if(i<=9985){
if(e>di){
ans={i,ans.second};
di=e;
return 4;
}
int shft=(i-9979)*2;
bool t1=0,t2=0;
if(((ans.first>>shft)&1))t1=1;
shft++;
if(((ans.first>>shft)&1))t2=1;
int x=t1;
if(t2)x+=2;
//cout<<shft<<' '<<ans.first<<' '<<x<<endl;
return x;
}
else{
e=0; lk=ans.first;
dfs(i,-1);
if(e>di){
ans={ans.first,i};
di=e;
return 4;
}
int shft=(i-9986)*2;
bool t1=0,t2=0;
if(((ans.second>>shft)&1))t1=1;
shft++;
if(((ans.second>>shft)&1))t2=1;
int x=t1;
if(t2)x+=2;
return x;
}
}
adj[i].pb(Pi);
adj[Pi].pb(i);
if(i>=9993){
// cout<<ans.first<<' '<<ans.second<<endl;
lk=ans.first; e=0;
dfs(i,-1); //we have replaced second dude
if(e>0){
ans.second=i;
di=e;
return 2;
}
lk=ans.second; e=0;
dfs(i,-1); //we have replaced first dude
if(e>0){
ans.first=i;
di=e;
return 3;
}
lk=i-7; e=0;
dfs(i,-1);
if(e>0){
ans={i,i-7};
di=e;
return 4;
}
if(ans.second!=i-7){
lk=ans.second; e=0;
dfs(i-7,-1);
if(e>0){
ans.first=i-7;
di=e;
return 1;
}
}
}
return 0;
}
std::pair<int, int> longest_path(std::vector<int> S) {
int x=0,y=0,p=1;
bool fl=0;
for(int i=9979;i<9993;i++){
if(i==9986){
p=1;
fl=0;
}
if(S[i]==4){
if(i<=9985)x=i;
else y=i;
fl=1;
}
if(fl)continue;
if(S[i]==1 || S[i]==3){
if(i<=9985)x+=p;
else y+=p;
}
p*=2;
if(S[i]==2 || S[i]==3){
if(i<=9985)x+=p;
else y+=p;
}
p*=2;
}
// cout<<x<<' '<<y<<endl;
for(int i=9993;i<=9999;i++){
if(S[i]==0)continue;
if(S[i]==4){
x=i; y=i-7;
continue;
}
if(S[i]==1)x=i-7;
if(S[i]==2)y=i;
if(S[i]==3)x=i;
}
return {x,y};
}
