#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;
const int D=14,MX=10005;
int jp[MX][D],dep[MX],ct[10],wl[15],n,sz0,sz1,szw;
pair<int,int>diam,pv,cd0[MX],cd1[MX],cp[15];
int szcp;
const pair<int,int>pt[5][5]={{{0,4},{0,5},{0,6},{0,8},{8,4}},{{0,7},{1,7},{1,4},{1,8},{8,7}},{{1,5},{1,6},{2,6},{2,8},{8,6}},{{2,4},{2,5},{3,5},{3,8},{8,5}},{{3,4},{3,6},{3,7},{2,7},{0,0}}};
int lca(int a,int b){
dep[a]<dep[b]?swap(a,b),0:0;
for(int d=D-1;d>=0;d--)(dep[a]-dep[b])&(1<<d)?(a=jp[a][d]):0;
for(int d=D-1;d>=0;d--)jp[a][d]!=jp[b][d]?(a=jp[a][d],b=jp[b][d]):0;
return jp[a][0];
}
int ds(int a,int b){return dep[a]+dep[b]-2*dep[lca(a,b)];}
void ex(pair<int,int>*v,int&sv,int pr,int r){
while(sv%pr)v[sv++]=v[sv-1];
int ns=sv/pr,st=ns*r;
for(int i=0;i<ns;i++)v[i]=v[st+i];
sv=ns;
}
int ix(pair<int,int>*v,int&sv,int g,int pr){
while(sv%pr)v[sv++]=v[sv-1];
int i=0;
while(v[i].first!=g)i++;
int r=i*pr/sv;
ex(v,sv,pr,r);
return r;
}
void ic(int N){ct[0]=N-173,ct[1]=N-33,ct[2]=N-13,ct[3]=N-7,ct[4]=N-5,ct[5]=N-3,ct[6]=N;}
bool cm(pair<int,int>a,pair<int,int>b){return a.first==b.first||a.first==b.second||a.second==b.first||a.second==b.second;}
void aa(int nv){
pair<int,int>tmp[15];
int st=0;
for(int i=0;i<szcp;i++)tmp[st++]=cp[i];
for(int i=0;i<szcp;i++)tmp[st++]={cp[i].first,nv},tmp[st++]={cp[i].second,nv};
sort(tmp,tmp+st),szcp=0;
for(int i=0;i<st;i++)if(!i||tmp[i]!=tmp[i-1])cp[szcp++]=tmp[i];
}
void vo(){
sort(cp,cp+szcp);
do{
bool ok=1;
for(int i=0;i+1<szcp;i+=2)if(!cm(cp[i],cp[i+1])){ok=0;break;}
if(ok)return;
}while(next_permutation(cp,cp+szcp));
}
pair<int,int>pe(pair<int,int>t){return{wl[t.first],wl[t.second]};}
bool eq(pair<int,int>a,pair<int,int>b){return(a.first==b.first&&a.second==b.second)||(a.first==b.second&&a.second==b.first);}
int c2(int x){return x*(x+1)/2;}
int send_message(int N,int i,int Pi){
if(i==1){
n=N,memset(jp,0,sizeof jp),memset(dep,0,sizeof dep),sz0=1,sz1=1,cd0[0]={0,0},cd1[0]={0,0},diam={0,0};
ic(N);
}
jp[i][0]=Pi,dep[i]=dep[Pi]+1;
for(int d=1;d<D;d++)jp[i][d]=jp[jp[i][d-1]][d-1];
for(int j=0;j<2;j++)if(ds(i,j?diam.second:diam.first)>ds(diam.first,diam.second)){j?diam.first=i:diam.second=i;break;}
int ci=0,mg=0;
while(ct[ci+1]<=i)ci++;
if(ci>0&&ct[ci]==i)for(int j=ct[ci-1]+1;j<ct[ci];j++)cd0[sz0++]={j,0},cd1[sz1++]={j,0};
if(i>=ct[5]){
if(i==ct[5]){
szw=0;
for(int j=0;j<sz0;j++)wl[szw++]=cd0[j].first;
for(int j=0;j<sz1;j++)wl[szw++]=cd1[j].first;
wl[szw++]=i;
while(1){
bool f=0;
for(int k=0;k<5;k++)if(diam==pe(pt[mg][k]))f=1;
if(f)break;
mg++;
}
szcp=0;
for(int k=0;k<5;k++)if(pt[mg][k].first||pt[mg][k].second)cp[szcp++]=pt[mg][k];
}else if(i==ct[5]+1){
wl[szw++]=i;
aa(9);
vo();
while(szcp<10)cp[szcp]=cp[szcp-1],szcp++;
int r=0;
while(!eq(diam,pe(cp[r])))r++;
mg=r/2;
ex(cp,szcp,5,mg);
}else{
wl[szw++]=i;
aa(10);
while(!eq(diam,pe(cp[mg])))mg++;
}
}else if(i>=ct[0]){
if(i==ct[ci]){
cd0[sz0++]={i,0},cd1[sz1++]={i,0};
const int sp=ct[ci+1]-ct[ci],nc=4*sp+1;
int te=0;
if(!ci){
int sc=1;
while(c2(sc+1)<=nc)++sc;
diam.first<diam.second?swap(diam.first,diam.second),0:0,te=c2(ix(cd0,sz0,diam.first,sc))+ix(cd1,sz1,diam.second,sc);
}else{
int sc=sqrt(nc);
te=sc*ix(cd0,sz0,diam.first,sc)+ix(cd1,sz1,diam.second,sc);
}
te==4*sp?pv={-1,-1}:pv={i+te/4,1+te%4};
}
if(i==pv.first)mg=pv.second;
}else cd0[sz0++]={i,0},cd1[sz1++]={i,0};
return mg;
}
pair<int,int>longest_path(vector<int>S){
memset(dep,0,sizeof dep),memset(jp,0,sizeof jp);
sz0=0,sz1=0,diam={0,0};
int N=S.size();
ic(N);
for(int i=0;i<N;i++){
int ci=0;
while(ct[ci+1]<=i)ci++;
if(ci>0&&ct[ci]==i){
int sp=ct[ci]-ct[ci-1],nc=4*sp+1,sc=0,te=0;
ci==1?0:sc=sqrt(nc);
if(ci==1)while(c2(sc+1)<=nc)sc++;
pv==make_pair(-1,-1)?te=4*sp:te=(pv.first-ct[ci-1])*4+(pv.second-1);
pair<int,int>ix{};
if(ci==1){
while(c2(ix.first+1)<=te)++ix.first;
ix.second=te-c2(ix.first);
}else ix={te/sc,te%sc};
ex(cd0,sz0,sc,ix.first),ex(cd1,sz1,sc,ix.second);
for(int j=ct[ci-1]+1;j<ct[ci];j++)cd0[sz0++]={j,0},cd1[sz1++]={j,0};
}
int mg=S[i];
if(i>=ct[5]){
if(i==ct[5]){
szw=0;
for(int j=0;j<sz0;j++)wl[szw++]=cd0[j].first;
for(int j=0;j<sz1;j++)wl[szw++]=cd1[j].first;
wl[szw++]=i;
szcp=0;
for(int k=0;k<5;k++)if(pt[mg][k].first||pt[mg][k].second)cp[szcp++]=pt[mg][k];
}else if(i==ct[5]+1){
wl[szw++]=i;
aa(9);
vo();
while(szcp<10)cp[szcp]=cp[szcp-1],szcp++;
ex(cp,szcp,5,mg);
}else{
wl[szw++]=i;
aa(10);
return pe(cp[mg]);
}
}else if(i>=ct[0]){
if(i==ct[ci])pv={-1,-1},cd0[sz0++]={i,0},cd1[sz1++]={i,0};
mg?pv={i,mg},0:0;
}else cd0[sz0++]={i,0},cd1[sz1++]={i,0};
if(i==N-1)return{cd0[0].first,cd1[0].first};
}
return{0,0};
}
