#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
namespace {
vector<vector<int>> adj;
pair<int,int> dfs(int x,int p){
pair<int,int> ans = {-1,x};
for(int&i:adj[x])if(i!=p){
ans = max(ans,dfs(i,x));
}
ans.first++;
return ans;
}
int currL,currR,currBest;
}
int send_message(int N, int i, int Pi) {
if(i==1)adj.resize(N);
adj[i].emplace_back(Pi);
adj[Pi].emplace_back(i);
if(i==9978){
currL = dfs(0,-1).second;
currR = dfs(currL,-1).second;
currBest = dfs(currL,-1).first;
return 0;
}
if(i>9978 and i<9986){ // sending L phase
if(dfs(currR,-1).first!=currBest){
// replacing L
currL = i;
currBest++;
return 0;
}
if(dfs(currL,-1).first!=currBest){
currR = i;
currBest++;
}
int bits = (i-9978-1)*2;
return ((currL>>bits)&3)+1;
}
if(i>9985){ // sending R phase
int offset = 0;
if(dfs(currR,-1).first!=currBest){
// replacing L
currL = i;
currBest++;
offset = 2;
}
if(dfs(currL,-1).first!=currBest){
currR = i;
currBest++;
return 0;
}
int bits = (i-9985-1);
return (((currR>>bits)&1) + offset)+1;
}
return 0;
}
pair<int,int> longest_path(vector<int> S){
int currL = 0;
int currR = 0;
for(int i=9979;i<9986;i++){
// reading currL
if(S[i]==0)currL=i;
else {
int c = S[i]-1;
int bits = (i-9978-1)*2;
currL|=c<<bits;
}
}
for(int i=9986;i<10000;i++){
// reading currR
if(S[i]==0)currR=i;
else {
int c = S[i]-1;
if(c&2){
currL = i;
c&=1;
}
int bits = (i-9985-1);
currR|=c<<bits;
}
}
return {currL,currR};
}
