#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 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;
	}
}