#include "migrations.h"
#include <bits/stdc++.h>
#define exoworldgd cin.tie(0)->sync_with_stdio(0),cout.tie(0)
using namespace std;
using ll=long long;
vector<int>p,dep,c0,c1,csz={182,25,6,1,1,1,1,1};
int n,e1,e2,cst,cid;
int getd(int v){
if(dep[v]==-1)dep[v]=(v==0)?0:getd(p[v])+1;
return dep[v];
}
int lca(int u,int v){
while(u!=v)getd(u)>getd(v)?u=p[u]:v=p[v];
return u;
}
int dist(int u,int v){
int l=lca(u,v);
return getd(u)+getd(v)-2*getd(l);
}
int send_message(int N,int i,int Pi){
if(i==1){
n=N,p.assign(N,0),dep.assign(N,-1),e1=0,e2=0,cst=1,cid=0;
c0.clear(),c1.clear();
for(int j=0;j<N;j++)c0.push_back(j),c1.push_back(j);
}
p[i]=Pi,dep[i]=-1;
int d1=dist(i,e1),d2=dist(i,e2),cd=dist(e1,e2),nd=max({cd,d1,d2});
nd>cd?(d1>=d2?e2=i:e1=i,0):0;
c0.push_back(i),c1.push_back(i);
if(i==cst+csz[cid]-1||i==N-1){
int s0=c0.size(),s1=c1.size(),B=csz[cid],msg=0;
if(!cid){
int k=floor(sqrt(4.0*B+1)),ns0=(s0+k-1)/k,b0=-1,b1=-1;
for(int j=0;j<k;j++){
for(int x=j*ns0;x<min((j+1)*ns0,s0);x++)c0[x]==e1?b0=j:0;
for(int x=j*((s1+B-1)/k);x<min((j+1)*((s1+B-1)/k),s1);x++)c1[x]==e2?b1=j:0;
}
msg=b0*k+b1+1;
vector<int>nc0,nc1;
for(int j=b0*ns0;j<min((b0+1)*ns0,s0);j++)nc0.push_back(c0[j]);
for(int j=b1*((s1+B-1)/k);j<min((b1+1)*((s1+B-1)/k),s1);j++)nc1.push_back(c1[j]);
c0=nc0,c1=nc1;
}else if(s0<=4&&s1<=4){
int i0=-1,i1=-1;
for(int j=0;j<s0;j++)c0[j]==e1?i0=j:0;
for(int j=0;j<s1;j++)c1[j]==e2?i1=j:0;
msg=i0*s1+i1+1;
c0={e1},c1={e2};
}else{
int k=floor(sqrt(4.0*B+1)),ns=(s0+k-2)/k+1,b0=-1,b1=-1;
for(int j=0;j<k;j++){
for(int x=j*ns;x<min((j+1)*ns,s0);x++)c0[x]==e1?b0=j:0;
for(int x=j*ns;x<min((j+1)*ns,s1);x++)c1[x]==e2?b1=j:0;
}
msg=b0*k+b1+1;
vector<int>nc0,nc1;
for(int j=b0*ns;j<min((b0+1)*ns,s0);j++)nc0.push_back(c0[j]);
for(int j=b1*ns;j<min((b1+1)*ns,s1);j++)nc1.push_back(c1[j]);
c0=nc0,c1=nc1;
}
cid++,cst=i+1;
return msg;
}
return 0;
}
pair<int,int>longest_path(vector<int>S){
int N=S.size();
vector<int>c0,c1;
for(int j=0;j<N;j++)c0.push_back(j),c1.push_back(j);
int cid=0,cst=1;
for(int i=1;i<N;i++){
c0.push_back(i),c1.push_back(i);
if(S[i]&&cid<8){
int msg=S[i]-1,B=csz[cid],s0=c0.size(),s1=c1.size();
if(cid==0){
int k=floor(sqrt(4.0*B+1)),b0=msg/k,b1=msg%k,ns0=(s0+k-1)/k;
vector<int>nc0,nc1;
for(int j=b0*ns0;j<min((b0+1)*ns0,s0);j++)nc0.push_back(c0[j]);
for(int j=b1*((s1+B-1)/k);j<min((b1+1)*((s1+B-1)/k),s1);j++)nc1.push_back(c1[j]);
c0=nc0,c1=nc1;
}else if(s0<=4&&s1<=4){
int i0=msg/s1,i1=msg%s1;
return{c0[i0],c1[i1]};
}else{
int k=floor(sqrt(4.0*B+1)),b0=msg/k,b1=msg%k,ns=(s0+k-2)/k+1;
vector<int>nc0,nc1;
for(int j=b0*ns;j<min((b0+1)*ns,s0);j++)nc0.push_back(c0[j]);
for(int j=b1*ns;j<min((b1+1)*ns,s1);j++)nc1.push_back(c1[j]);
c0=nc0,c1=nc1;
}
cid++,cst=i+1;
}
}
return{c0[0],c1[0]};
}
