#include "migrations.h"
#include<bits/stdc++.h>
using namespace std;
vector<int> adj[10001];
vector<int> dist;
int p[10001];
pair<int,int> ans = {-1,-1};
int bst = 0;
void dfs(int u, int par) {
for (auto &v : adj[u]) {
if (v == par) continue;
dist[v] = dist[u] + 1;
dfs(v, u);
}
}
tuple<int,int,int> func(int n) {
dist.assign(n, 0);
dfs(0, -1);
int a = max_element(dist.begin(), dist.end()) - dist.begin();
dist.assign(n, 0);
dfs(a, -1);
int b = max_element(dist.begin(), dist.end()) - dist.begin();
int d = dist[b];
return {a, b, d};
}
int D(int x, int y,int n) {
dist.assign(n, 0);
dfs(x, -1);
return dist[y];
}
int send_message(int N, int i, int Pi) {
adj[i].emplace_back(Pi);
adj[Pi].emplace_back(i);
if(i < N-26){
return 0;
}else if(i==N-26){
tuple<int,int,int> oc = func(i+1);
bst = get<2>(oc);
ans = pair<int,int>{get<0>(oc),get<1>(oc)};
if(get<0>(oc) & (1<<((N-i)/2))){
return 1;
}else return 0;
}else{
tuple<int,int,int> oc = func(i+1);
int curr = get<2>(oc);
pair<int,int> ret = pair<int,int>{get<0>(oc),get<1>(oc)};
int u = ans.first;
int v = ans.second;
if(curr>bst){
int du = D(u,i,i+1);
int dv = D(v,i,i+1);
if(du == curr){
bst = curr;
ans = pair<int,int>{u,i};
if(i & 1){//if on v
return 4;
}else{// on u
if(u & (1<<((N-i)/2))){
return 3;
}else return 2;
}
} else{
bst = curr;
ans = pair<int,int>{i,v};
if(i & 1){
if(v & (1<<((N-i)/2))){
return 3;
}else return 2;
}else{
return 4;
}
}
}else{
if(i&1){
if(v & (1<<((N-i)/2))){
return 1;
}else return 0;
}else{
if(u & (1<<((N-i)/2))){
return 1;
}else return 0;
}
}
}
}
pair<int, int> longest_path(vector<int> S) {
int u = 0;
int v = 0;
bool cu = false;
bool cv = false;
int N =S.size();
if(S[N-26]){
u |= (1ll<<13);
}
for(int i = N-25; i <= N-1; ++i){
if(i & 1){
if(S[i] <= 1){
if(S[i] and !cv){
v |= (1ll<<((N-i)/2));
}
}else if(S[i] < 4){
if(S[i] == 3 and !cv){
v |= (1ll<<((N-i)/2));
}
u = i;
cu = true;
}else{
v = i;
cv = true;
}
}else{
if(S[i] <= 1){
if(S[i] and !cu){
u |= (1ll<<((N-i)/2));
}
}else if(S[i] < 4){
if(S[i] == 3 and !cu){
u |= (1ll<<((N-i)/2));
}
v = i;
cv = true;
}else{
u = i;
cu = true;
}
}
}
return pair<int,int>{u,v};
}
