#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 ask(int a,int b,int c)
{
	return 0;
}

int rand(int l,int r)
{
	return rnd()%(r-l+1)+l;
}

int get_fa(int u)
{
	if(bel[u]==u) return u;
	int fa=0;
	for(auto x:Link)
	{
		if(!fa) fa=x;
		else fa=ask(fa,u,x);
	}
	return fa;
} 

bool 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 u:ctr)
	{
		if(u==x||bel[u]!=-1) continue;
		if(!now||ask(now,x,u)!=x) now=(!now)?u:now,cnt++;
		else if((--cnt)==0) now=0;
	}
	if(!now||now==L||now==R) return true;
	cnt=0;
	for(auto u:ctr) 
	{
		if(u==x||bel[u]!=-1) continue;
		if(u==now||ask(now,x,u)!=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 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;
	}
}

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccHjykzV.o: in function `ask(int, int, int)':
answer.code:(.text+0x0): multiple definition of `ask(int, int, int)'; /tmp/cc81X14Z.o:implementer.cpp:(.text+0x1e0): first defined here
collect2: error: ld returned 1 exit status