#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 x)
{
	if(bel[x]==x)return x;//如果在链上，直接返回 
	int p=0;for(auto y:Link)if(!p)p=y;else p=ask(x,p,y);//不断更新，找到他的最近链上祖先 
	return p;
}

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 num[N];
int centroid(int id,int nn,int mm)
{
	int t=0;n=nn,m=mm;
	if(id==5)
	{
		int a=1,b=2;num[1]=1,num[2]=2;
		for(int i=3;i<=n;i++)
		{
			int t=ask(a,b,i);num[i]=i;
			if(t==a)a=i;else if(t==b)b=i;
		}
		nth_element(num+1,num+n/2+1,num+n+1,[=](const int&x,const int&y){return ask(a,x,y)!=x;});
		return num[n/2+1];
	}
	uniform_int_distribution<int>dist(1,n);
	if(nn==3)return ask(1,2,3);
	while(1)
	{
		ctr.clear();L=dist(rnd),R=dist(rnd),szl=szr=1;
		for(int i=1;i<=n;i++)if(i!=L&&i!=R)ctr.push_back(i);
		if((t=solve()))return t;
	}
}