#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ll long long
const int N=10050,lg=14;
vector<int>E[N];
int par[N+50][lg+2],depth[N+50];
int LCA(int u,int v){
if(depth[u]<depth[v]) swap(u,v);
for(int i=lg;i>=0;i--) if(depth[par[u][i]]>=depth[v]) u=par[u][i];if(u==v) return u;
for(int i=lg;i>=0;i--) if(par[u][i]!=par[v][i]) u=par[u][i],v=par[v][i];return par[u][0];
}
int Dist(int u,int v){return depth[u]+depth[v]-2*depth[LCA(u,v)];}
/*int dist[N];
void DFS(int u,int p=-1){
if(p==-1) dist[u]=0;
else dist[u]=dist[p]+1;
for(auto i:E[u]) if(i!=p) DFS(i,u);
}
int Dist1(int u,int v){
DFS(u);
return dist[v];
}*/
int U,V,num[2];
int send_message(int n,int i,int Pi){
i++,Pi++;
if(i==2){
U=V=1;
}
E[i].pb(Pi);E[Pi].pb(i);
depth[i]=depth[Pi]+1;
par[i][0]=Pi;
for(int j=1;j<=lg;j++) par[i][j]=par[par[i][j-1]][j-1];
if(Dist(U,V)<Dist(i,V)) U=i;
if(Dist(U,V)<Dist(U,i)) V=i;
//printf("%i %i: %i %i\n",i,Pi,U,V);
if(i<n-49) return 0;
if(i==U){
num[0]=lg;
return 3;
}
if(i==V){
num[1]=lg;
return 4;
}
if(num[0]<lg){
int bit=((U-1)>>num[0])&1;
num[0]++;
return bit+1;
}
if(num[1]<lg){
int bit=((V-1)>>num[1])&1;
num[1]++;
return bit+1;
}
return 0;
}
pair<int,int>longest_path(vector<int>S){
int n=S.size();
int U=0,V=0;
int num[2]={0};
for(int i=0;i<n;i++){
if(S[i]==0) continue;
if(S[i]==3){
num[0]=lg;
U=i;
}
else if(S[i]==4){
num[1]=lg;
V=i;
}
else{
if(num[0]<lg){
if(S[i]==2) U+=(1<<num[0]);
num[0]++;
}
else if(num[1]<lg){
if(S[i]==2) V+=(1<<num[1]);
num[1]++;
}
}
//printf("{%i %i}\n",U,V);
}
return {U,V};
}
