#include <bitsdc++.h>
//#include "soul.h"
using namespace std;
const int NN=4e6+3;
int n,anss,a[NN],ba[NN],bb[NN],bc[NN];
int siz[NN],maxn[NN],ru[NN],dui[NN];
int v[NN],nt[NN],h[NN],cnt;
int vx[NN],ntx[NN],hx[NN],cntx;
int ask(int x,int y,int z);
void add(int x,int y){
	v[++cnt]=y;
	nt[cnt]=h[x];
	h[x]=cnt;
}
void _add(int x,int y){
	vx[++cntx]=y;
	ntx[cntx]=hx[x];
	hx[x]=cntx;
}
void dfss(int x){
	siz[x]=1;maxn[x]=0;
	for(int i=hx[x];i;i=ntx[i]){
		dfss(vx[i]),siz[x]+=siz[vx[i]];
		if(siz[maxn[x]]<siz[vx[i]])maxn[x]=vx[i];
	}
	if(max(siz[maxn[x]],n-siz[x])<max(siz[maxn[anss]],n-siz[anss]))
		anss=x;
}
int dfs(int l,int r,int k){
	if(l==r)return a[l];
	int lx=rand()%(r-l+1)+l,rx;
	do{
		rx=rand()%(r-l+1)+l;
	}while(rx==lx);
	if(lx>rx)swap(lx,rx);
	int sumx=0,sumy=0,sumz=0;
	for(int i=l;i<=r;++i)
	if(i!=lx&&i!=rx){
		int zhong=ask(a[lx],a[i],a[rx]);
		if(zhong==a[lx])ba[++sumx]=a[i];
		if(zhong==a[i])bb[++sumy]=a[i];
		if(zhong==a[rx])bc[++sumz]=a[i];
	}
//	cout<<l<<' '<<r<<' '<<k<<' '<<sumx<<' '<<sumy<<' '<<sumz<<' '<<lx<<' '<<rx<<'\n';
	if(sumx+1>k){
		for(int i=1,ii=l;i<=sumx;++i,++ii)
		a[ii]=ba[i];
		return dfs(l,l+sumx-1,k);
	}
	if(sumx+1==k)return a[lx];
	if(sumx+1+sumy+1>k){
		for(int i=1,ii=l;i<=sumy;++i,++ii)
		a[ii]=bb[i];
		return dfs(l,l+sumy-1,k-sumx-1);
	}
	if(sumx+sumy+2==k)return a[rx];
	for(int i=1,ii=l;i<=sumz;++i,++ii)
	a[ii]=bc[i];
	return dfs(l,l+sumz-1,k-sumx-sumy-2);
}
int centroid(int id,int N,int M){
	srand(time(0));n=N;
	if(N<=3)return ask(1,2,3);
	else if(id!=3&&id!=5){
		int rt=1;
		for(int i=1;i<=n;++i)h[i]=ru[i]=siz[i]=maxn[i]=hx[i]=0;
		cnt=cntx=0;
		for(int i=1;i<=n;++i)
		if(i!=rt){
			for(int j=i+1;j<=n;++j)
			if(j!=rt){
				int zhong=ask(rt,i,j);
				if(zhong==i)add(i,j),++ru[j];
				if(zhong==j)add(j,i),++ru[i];
			}
		}
		for(int i=1;i<=n;++i)
		if(i!=rt)add(rt,i),++ru[i];
		int l=0,r=1;dui[1]=rt;
		while(l<r){
			int x=dui[++l];
			for(int i=h[x];i;i=nt[i]){
				if(!(--ru[v[i]]))dui[++r]=v[i],_add(x,v[i]);
			}
		}
		dfss(rt);
		return anss;
	}
	else{
		for(int i=1;i<=n;++i)a[i]=i;
//		cout<<dfs(1,n,(1+n)/2)<<'\n';
		return dfs(1,n,(1+n)/2);
	}
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:60:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |         fread(Interactor::rbuf,1,50000000,stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code:1:10: fatal error: bitsdc++.h: No such file or directory
    1 | #include <bitsdc++.h>
      |          ^~~~~~~~~~~~
compilation terminated.