#include<bits/stdc++.h>
#include " path.h "
#define re register
using namespace std;
int Ans,O,num,n;
bool cmp(int x,int y){
	return ask(O,x,y)==x;
}
mt19937 rng(time(0));
void solve(vector<int> A,vector<int> B,re int x,re int y,re int L,re int R)
{
	int pos=rng()%(A.size()+B.size()),o;
	if(pos<A.size()) o=A[pos];
	else o=B[pos-A.size()];
	vector<int> LA,LB,RA,RB;
	re int curx=0;
	for(int z:A)
	{
		re int p1=ask(x,o,z),p2=ask(y,o,z);
		if(p1==z&&p2==z) curx=z;
		else if(p1==z) LA.push_back(z);
		else RA.push_back(z);
	}
	re int s1=0,s2=L+LA.size(),s3=R+RA.size();
	for(int z:B)
	{
		re int p1=ask(x,curx,z),p2=ask(y,curx,z);
		if(p1==curx&&p2==curx) ++s1;
		else if(p1==curx) RB.push_back(z),s3++;
		else LB.push_back(z),s2++;
	}
	if(s1+s1>n)
	{
		re int pos=(L<=R) ? y:x,ans=abs(R-L);
		for(int z:B){
			re int pp=ask(pos,z,curx);
			if(pp==curx)
		    {
		    	if(!ans) pos=z,ans=1;
		    	else --ans;
			}
			else ++ans;
		}
		for(int z:A)
		if(z^curx)
		{
			int pp=ask(pos,z,curx);
			if(pp==curx)
			{
				if(!ans) pos=z,ans=1;
				else ans--;
			}
			else ans++;
		}
	 int s=0;
		for(int z:B)
		{
			re int pp=ask(z,pos,curx);
			if(pp^curx) ++s;
		}
		for(int z:A) 
		if(z^curx)
		{
			re int pp=ask(z,pos,curx);
			if(pp^curx)++s;
		}
		if(s+s<n) 
		Ans=curx;
		return ;
	}
	if(s1+s1<n&&s2+s2<n&&s3+s3<n) {Ans=curx;return ;}
	if(s2+s2>n) solve(LA,LB,x,y,L,s1+s3+1);
	else solve(RA,RB,x,y,s1+s2+1,R);
}
void Try(re int x,re int y){
	vector<int> A,B;
	for(re int i=1;i<=n;i++)
	{
		int o=ask(x,y,i);
		if(o==i) A.push_back(i);
		else B.push_back(i);
	}
	solve(A,B,x,y,0,0);
}
int centroid(int id,int n,int m)
{
	srand(time(0));
	if(id==1){
		return ask(1,2,3);
	}
	else if(id==3||id==5){
		Ans=0,O=1;
		int x=1,y=2;
		for(int i=3;i<=n;i++)
		{
			int pp=ask(x,y,i);
			if(pp==y) y=i;
			else if(pp==x) x=i;
		}O=x;
		vector<int> A;
		for(int i=1;i<=n;i++) A.push_back(i);
		nth_element(A.begin(),A.begin()+(n+1)/2-1,A.end(),cmp);
		return A[n>>1];
	}
	while(1)
	{
		num=0;
		re int x=rng()%(n)+1,y=rng()%(n)+1;
		while(x==y) y=rng()%(n)+1;
		Ans=0;Try(x,y);
		if(Ans) return Ans;
	}
}

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:2:10: fatal error:  path.h : No such file or directory
    2 | #include " path.h "
      |          ^~~~~~~~~~
compilation terminated.