#include"path.h"
#include<bits/stdc++.h>
#define pb push_back
using namespace std;
const int N=5e4+100;
int n,m,l,r,sizl,sizr;
int bel[N];
mt19937 rd(time(0));
vector<int>lst,st;
int getfa(int x)
{
	if(bel[x]==x)return x;
	int p=0;for(auto y:lst)if(!p)p=y;else p=ask(x,p,y);
	return p;
}
int check(int x,int lc,int rc)
{
	int cnt=0,now=0;
	if(lc!=rc)cnt=abs(lc-rc),now=lc>rc?l:r;
	for(auto y:st)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:st)if(x!=y&&bel[y]==-1)if(y==now||ask(x,now,y)!=x)cnt++;
	return cnt*2<=n;
}
int solve()
{
	if(l==r||!st.size())return 0;
	if(sizl*2>n||sizr*2>n)return 0;
	uniform_int_distribution<int>dist(0,st.size()-1);
	int p=getfa(st[dist(rd)]);
	int lc=sizl,rc=sizr,tot=0;
	for(auto x:st)
	{
		if(x==p)continue;
		if(ask(x,l,p)!=p)bel[x]=0,lc++;
		else if(ask(x,r,p)!=p)bel[x]=1,rc++;
		else bel[x]=-1,tot++;
	}
	if(lc*2<=n&&rc*2<=n)if(check(p,lc,rc))return p;
	if(lc>rc)r=p,sizr=rc+1+tot;else l=p,sizl=lc+1+tot;
	vector<int>vt(st);lst.clear();st.clear();
	for(auto x:vt)
	{
		if(bel[x]!=(lc<rc))continue;
		if(ask(x,l,r))lst.pb(x);st.pb(x);
	}
	return solve();
}
int centroid(int id,int nn,int mm)
{
	if(id>5)exit(0);
	int t=0;n=nn,m=mm;
	uniform_int_distribution<int>dist(1,n);
	if(nn==3)return ask(1,2,3);
	while(1)
	{
		memset(bel,0x3f,sizeof(bel));
		st.clear();l=dist(rd),r=dist(rd);sizl=sizr=0;
		for(int x=1;x<=n;x++)
		{
			int t=ask(l,x,r);
			if(t==l)sizl++;
			else if(t==r)sizr++;
			else if(t)lst.pb(x),st.pb(x);
			else st.pb(x);
		}
		if((t=solve()))return t;
	}
}