// idea from looking at other solutions
#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<tuple<int,int,int,int,bool>>ph;
int n,p1,p2,q1,q2,q3,r1,r2,r3,lu,lv,pr;
vector<int>cp,cq,g[10005];
pair<int,int>dl;
int pb(int m){
int bb=1,bf=1e9,lm=2*cbrt(m+1)+2;
for(int b=1,f;b<=lm;b++)f=(m+1+b-1)/b+((b*b-1+3)/4)-1,f<bf?(bf=f,bb=b):0;
return bb;
}
int pf(int m){
int bb=1,bf=1e9,lm=2*cbrt(m+1)+2;
for(int b=1,st,f;b<=lm;b++)st=b*(b+1)/2,f=(m+1+b-1)/b+((st-1+3)/4)-1,f<bf?(bf=f,bb=b):0;
return bb;
}
void calc(){
for(int i=4;i<n-3;i++){
ph.clear();
int m=i-1,ps=i-1;
bool fr=1;
while(ps<n-3&&ph.size()<5){
int b=fr?pf(m):pb(m),k=fr?((b*(b+1)/2-1+3)/4):((b*b-1+3)/4);
ph.push_back(make_tuple(m,b,k,ps,fr));
m=(m+b-1)/b+k-1,ps+=k,fr=0;
}
reverse(ph.begin(),ph.end());
if(ps==n-3&&ph.size()==5&&m<=4)break;
}
}
vector<int>sl(const vector<int>&c,int bu,int b){int s=bu*b,e=min((int)c.size(),s+b);return vector<int>(c.begin()+s,c.begin()+e);}
int bf(int sr){
int d[n];
queue<int>q;
memset(d,-1,sizeof d),d[sr]=0,q.push(sr);
for(int u;q.size();)u=q.front(),q.pop(),for(int v:g[u])d[v]<0?(d[v]=d[u]+1,q.push(v)):0;
return max_element(d,d+n)-d;
}
pair<int,int>dm(){int u=bf(0),v=bf(u);return{u,v};}
bool sm(pair<int,int>a,pair<int,int>b){
a.first>a.second?swap(a.first,a.second):0;
b.first>b.second?swap(b.first,b.second):0;
return a==b;
}
int send_message(int N,int i,int p){
if(N<=9){
if(i==1){for(int j=0;j<N;j++)g[j].clear();lu=0,lv=1;}
g[i].push_back(p),g[p].push_back(i);
if(i>=2){
n=N;
auto[u,v]=dm();
u>v?swap(u,v):0;
int ms=u==lu&&v==lv?0:(v^lv&&u==lu?1:2);
lu=u,lv=v;
return ms;
}
return 0;
}
if(i==1){n=N,calc(),cp={0},cq={0},dl={-1,-1};for(int j=0;j<N;j++)g[j].clear();}
g[i].push_back(p),g[p].push_back(i);
i<n-3?(cp.push_back(i),cq.push_back(i)):0;
if(i==get<3>(ph.back())){
auto[u,v]=dm();
auto[m,b,k,st,tr]=ph.back();
find(cp.begin(),cp.end(),u)==cp.end()||find(cq.begin(),cq.end(),v)==cq.end()?swap(u,v):0;
int iu=find(cp.begin(),cp.end(),u)-cp.begin(),iv=find(cq.begin(),cq.end(),v)-cq.begin(),bs=ceil((double)m/b),bu=iu/bs,bv=iv/bs;
cp=sl(cp,bu,bs),cq=sl(cq,bv,bs);
if(tr){
u>v?(swap(u,v),swap(cp,cq),swap(bu,bv)):0;
int ix=0;
for(int x=0;x<bu;x++)ix+=b-x;
ix+=bv-bu;
ix>=0?(dl={i+(ix-1)/4,((ix-1)%4)+1}):0;
}else{int cl=bu*b+bv;cl?(dl={i+(cl-1)/4,((cl-1)%4)+1}):0;}
ph.pop_back();
}
if(i==dl.first)return dl.second;
if(i==n-3){
while(cp.size()<4)cp.push_back(0);
while(cq.size()<4)cq.push_back(0);
vector<pair<int,int>>cd={{cp[0],cq[0]},{cp[0],cq[1]},{cp[0],cq[2]},{cp[1],cq[0]},{cp[1],cq[1]},{cp[0],cq[3]},{cp[0],i},{cp[1],cq[2]},{cp[1],cq[3]},{cp[1],i},{cp[2],cq[0]},{cp[2],cq[1]},{cp[3],cq[0]},{cp[3],cq[1]},{i,cq[0]},{cp[2],cq[2]},{cp[2],cq[3]},{cp[2],i},{cp[3],cq[3]},{cp[3],i},{cp[3],cq[2]},{i,cq[1]},{i,cq[2]},{i,cq[3]}};
auto[u,v]=dm();
find(cd.begin(),cd.end(),make_pair(u,v))==cd.end()?swap(u,v):0;
return pr=(find(cd.begin(),cd.end(),make_pair(u,v))-cd.begin())/5;
}
if(i==n-2){
int a1=cp[0],a2=cp[1],a3=cp[2],a4=cp[3],b1=cq[0],b2=cq[1],b3=cq[2],b4=cq[3];
pr==0?(p1=a1,p2=a2,q1=b1,q2=b2,q3=b3):pr==1?(p1=a2,p2=a1,q1=i-1,q2=b4,q3=b3):pr==2?(p1=b1,p2=b2,q1=a3,q2=a4,q3=i-1):pr==3?(p1=a3,p2=a4,q1=i-1,q2=b4,q3=b3):(p1=i-1,p2=a4,q1=b2,q2=b3,q3=b4);
vector<pair<int,int>>cd={{p1,q1},{p2,q1},{p1,q2},{p2,q2},{p1,q3},{i,q3},{i,q1},{i,q2},{p1,i},{p2,i}};
auto[u,v]=dm();
find(cd.begin(),cd.end(),make_pair(u,v))==cd.end()?swap(u,v):0;
return pr=(find(cd.begin(),cd.end(),make_pair(u,v))-cd.begin())/2;
}
if(i==n-1){
pr==0?(r3=q1,r2=p1,r1=p2):pr==1?(r3=q2,r2=p1,r1=p2):pr==2?(r3=q3,r2=p1,r1=n-2):pr==3?(r3=n-2,r2=q1,r1=q2):(r3=n-2,r2=p1,r1=p2);
auto[u,v]=dm();
return sm({u,v},{r1,r3})?0:sm({u,v},{r2,r3})?1:sm({u,v},{r1,i})?2:sm({u,v},{r2,i})?3:4;
}
return 0;
}
pair<int,int>longest_path(vector<int>S){
int N=S.size(),ps=0;
n=N;
if(N<=9){
int u=0,v=1;
for(int i=1;i<N;i++)S[i]==1?v=i:(S[i]==2?(u=v,v=i):0);
return{u,v};
}
cp.clear(),cq.clear(),calc();
while(ph.size()){
auto[m,b,k,st,tr]=ph.back();
while(ps^st+1)cp.push_back(ps),cq.push_back(ps),ps++;
int c=0,mg=-1;
for(int i=ps-1;i<ps+k-1;i++)S[i]?mg=S[i]:c++;
int cl=mg==-1?0:c*4+mg,bu=0,bv=0,bs=ceil((double)m/b);
if(tr){
cl++;
for(int u=0;u<b;u++){
int rw=b-u;
if(cl<=rw){bu=u,bv=u+cl-1;break;}
cl-=rw;
}
}else bu=cl/b,bv=cl%b;
cp=sl(cp,bu,bs),cq=sl(cq,bv,bs);
for(int i=ps;i<ps+k-1;i++)cp.push_back(i),cq.push_back(i);
ps+=k-1,ph.pop_back();
}
while(cp.size()<4)cp.push_back(0);
while(cq.size()<4)cq.push_back(0);
int a1=cp[0],a2=cp[1],a3=cp[2],a4=cp[3],b1=cq[0],b2=cq[1],b3=cq[2],b4=cq[3];
!S[N-3]?(p1=a1,p2=a2,q1=b1,q2=b2,q3=b3):S[N-3]==1?(p1=a2,p2=a1,q1=N-3,q2=b4,q3=b3):S[N-3]==2?(p1=b1,p2=b2,q1=a3,q2=a4,q3=N-3):S[N-3]==3?(p1=a3,p2=a4,q1=N-3,q2=b4,q3=b3):(p1=N-3,p2=a4,q1=b2,q2=b3,q3=b4),!S[N-2]?(r3=q1,r2=p1,r1=p2):S[N-2]==1?(r3=q2,r2=p1,r1=p2):S[N-2]==2?(r3=q3,r2=p1,r1=N-2):S[N-2]==3?(r3=N-2,r2=q1,r1=q2):(r3=N-2,r2=p1,r1=p2);
return !S[N-1]?make_pair(r1,r3):S[N-1]==1?make_pair(r2,r3):S[N-1]==2?make_pair(r1,N-1):S[N-1]==3?make_pair(r2,N-1):make_pair(r3,N-1);
}
