#include "migrations.h"
#include <bits/stdc++.h>
using namespace std;
int dist[10000];
int high = 0;
int P[10000];
int binary[10000][14];
int first = 0;
int second = 0;
int lca(int i,int j){
if(dist[i]<dist[j]){
swap(i,j);
}
for(int k=13;k>=0;k--){
if(dist[i]-(1<<k)>=dist[j]){
i = binary[i][k];
}
}
if(i==j){
return i;
}
for(int k=13;k>=0;k--){
if(binary[i][k]!=binary[j][k]){
i = binary[i][k];
j = binary[j][k];
}
}
return P[i];
}
int distance(int i,int j){
return dist[i]+dist[j]-2*dist[lca(i,j)];
}
int send_message(int N, int i, int Pi){
dist[i] = dist[Pi]+1;
P[i] = Pi;
binary[i][0] = Pi;
for(int j=1;j<14;j++){
binary[i][j] = binary[binary[i][j-1]][j-1];
}
int x = distance(first,second);
if(distance(first,i)>x){
second = i;
}
if(distance(second,i)>x){
first = i;
}
if(i>=N-28){
int x = (N-1-i)/2;
if(i&1){
if(first==i){
return 0;
}
int a = 1;
if(second==i){
a += 2;
}
if(first&(1<<x)){
a++;
}
return a;
}
else{
if(second==i){
return 0;
}
int a = 1;
if(first==i){
a += 2;
}
if(second&(1<<x)){
a++;
}
return a;
}
}
return 0;
}
pair<int,int> longest_path(vector<int> S){
int n = S.size();
pair<int,int> ans;
ans.first = -1;
ans.second = -1;
int a = 0;
int b = 0;
for(int i=n-28;i<n;i++){
if(i&1){
if(S[i]==0){
ans.first = i;
}
if(S[i]>=3){
ans.second = i;
}
if(S[i]==2||S[i]==4){
a += (1<<(n-1-i)/2);
}
}
else{
if(S[i]==0){
ans.second = i;
}
if(S[i]>=3){
ans.first = i;
}
if(S[i]==2||S[i]==4){
b += (1<<(n-1-i)/2);
}
}
}
if(ans.first==-1){
ans.first = a;
}
if(ans.second==-1){
ans.second = b;
}
return ans;
}
