#include"path.h"
#include<bits/stdc++.h>
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[x]==-1)
		if(!now||ask(now,x,y)!=now)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[x]==-1)if(y==now||ask(x,now,y)!=x)cnt++;
	return cnt*2<=n;
}
int solve()
{
	if(l==r||!st.size())return 0;
	vector<int>vt(st);st.clear();lst.clear();
	for(auto x:vt)
	{
		if(x==l||x==r)continue;
		bel[x]=ask(l,x,r);
		if(bel[x]==l)sizl++;
		else if(bel[x]==r)sizr++;
		else if(bel[x]==x)lst.push_back(x),st.push_back(x);
		else st.push_back(x);
	}
	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;
	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;
	}
	if(lc*2<=n&&rc*2<=n)if(check(p,lc,rc))return p;
	if(lc>rc)r=p,sizr++;else l=p,sizl++;
	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)
	{
		st.clear();l=dist(rd),r=dist(rd),sizl=sizr=1;
		for(int i=1;i<=n;i++)if(i!=l&&i!=r)st.push_back(i);
		if((t=solve()))return t;
	}
}