//#include"path.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,m,L,R,szl,szr,wc;
int bel[N],p[N];
vector<int> Link,ctr;
mt19937 rnd(time(0));
int rand(int l,int r)
{
return rnd()%(r-l+1)+l;
}
//int ask(int a,int b,int c)
//{
// return 0;
//}
int get_fa(int u)
{
if(bel[u]==u) return u;
int fa=0;
for(auto x:Link)
{
if(!fa) fa=x;
else fa=ask(fa,u,x);
}
return fa;
}
int check(int x,int lc,int rc)//把x子树中的点拿出来，投出来x子树大小最大的儿子 ，每次询问(now,x,y)可以知道now和y是否在一棵子树
{
int cnt=0,now=0;
if(lc!=rc)cnt=abs(lc-rc),now=lc>rc?L:R;
for(auto y:ctr)if(x!=y&&bel[y]==-1)
if(!now||ask(now,x,y)!=x)now=!now?y:now,cnt++;
else if(--cnt==0)now=0;
if(!now||now==L||now==R)return 1;//如果没有绝对众数
cnt=0;
for(auto y:ctr)if(x!=y&&bel[y]==-1)if(y==now||ask(x,now,y)!=x)cnt++;//统计一下和他在一棵子树内的部分
return cnt*2<=n;
}
//
//int solve()
//{
// if(L==R||ctr.size()==0) return 0;
// vector<int> vec;vec=ctr;
// ctr.clear(),Link.clear();
// for(auto x:vec)
// {
// if(x==L||x==R) continue;
// bel[x]=ask(L,x,R);
// if(bel[x]==L) szl++;
// else if(bel[x]==R) szr++;
// else if(bel[x]==x) Link.push_back(x),ctr.push_back(x);
// else ctr.push_back(x);
// }
// if(szl*2>n||szr*2>n) return 0;
// int nw=get_fa(ctr[rand(0,ctr.size()-1)]);
// int lc=szl,rc=szr;
// for(auto x:ctr)
// {
// if(x==nw) continue;
// if(ask(x,L,nw)!=nw) bel[x]=0,lc++;
// else if(ask(x,R,nw)!=nw) bel[x]=1,rc++;
// else bel[x]=-1;
// }
// if(lc*2<=n&&rc*2<=n&&check(nw,lc,rc)) return nw;
// if(lc>rc) R=nw,szr++;
// else L=nw,szl++;
// return solve();
//}
int solve()
{
if(L==R||!ctr.size())return 0;
vector<int> vt(ctr);
ctr.clear();//不在链两端子树中的点集
Link.clear();//在链上的点集
for(auto x:vt)
{
if(x==L||x==R)continue;
bel[x]=ask(L,x,R);//标记属于l的子树，r的子树或链上的点
if(bel[x]==L) szl++;//在链左端的点
else if(bel[x]==R)szr++;//在链右端的点
else if(bel[x]==x) Link.push_back(x),ctr.push_back(x);//正好在链上的点
else ctr.push_back(x);//不在链上的点且不是左右两端子树中的
}
if(szl*2>n||szr*2>n)return 0;//左右两子树已经超限
uniform_int_distribution<int>dist(0,ctr.size()-1);
int nw=get_fa(ctr[dist(rnd)]);//随机在链上选一个不在两端的点
int lc=szl,rc=szr;
for(auto x:ctr)//统计p链左子树大小和p链右子树大小
{
if(x==nw)continue;
if(ask(x,L,nw)!=nw) bel[x]=0,lc++;//在链上p左侧的子树中
else if(ask(x,R,nw)!=nw) bel[x]=1,rc++;//在链上p右侧的子树中
else bel[x]=-1;//恰在p的子树内
}
if(lc*2<=n&&rc*2<=n)if(check(nw,lc,rc))return nw;
if(lc>rc)R=nw,szr++;else L=nw,szl++;//往子树大小大的方向移动
return solve();
}
int centroid(int id,int N,int M)
{
n=N,m=M;
if(id==5)
{
int a=1,b=2;
p[1]=1,p[2]=2;
for(int i=3;i<=n;i++)
{
p[i]=i;
int mid=ask(a,b,i);
if(mid==a) a=i;
else if(mid==b) b=i;
}
nth_element(p+1,p+n/2+1,p+n+1,[=](const int&x,const int&y){return ask(a,x,y)!=x;});
return p[n/2+1];
}
if(n==3) return ask(1,2,3);
while(true)
{
Link.clear();
L=rand(1,n),R=rand(1,n);
for(int u=1;u<=n;u++)
{
if(u!=L&&u!=R) ctr.push_back(u);
}
szl=szr=1;
if((wc=solve())) return wc;
}
}