#include<bits/stdc++.h>
#include "soul.h"
using namespace std;
map<array<int,3>,int>M;
inline int ASK(int x,int y,int z)
{
	if(x==y)return x;
	if(y==z)return y;
	if(x==z)return x;
	array<int,3>a={x,y,z};
	sort(a.begin(),a.end());
	return ask(x,y,z);
//	 if(M.count(a))return M[a];
//	 return M[a]=ask(x,y,z);
}
int n,bn[101000];
mt19937 rnd(43525);
inline bool jud(int x)
{
	if(bn[x])return false;
//	cerr<<"JUDGE: "<<x<<endl;
	vector<int>V;
	for(int i=1;i<=n;++i)if(i!=x){
		if(!V.size())V={i};
		else if(ASK(V.back(),x,i)!=x)V.push_back(i);
		else V.pop_back();}
	int z=V[0],cnt=0;
//	cerr<<z<<endl;
	for(int i=1;i<=n;++i)if(i!=x)
		if(ASK(z,x,i)!=x)++cnt;
//	cerr<<cnt<<endl;
bn[x]=1;
	if(cnt>n/2)return false;
	return true;
}
int ans=0;
int solve()
{
	for(int i=1;i<=n;++i)bn[i]=0;
	int W=0;
	while(1)
	{
		++W;
		cerr<<W<<endl;
		int u=rnd()%n+1,v=rnd()%n+1;
		if(u==v)continue;
		vector<int>z,Z;
		int va=0,vb=0;
		for(int i=1;i<=n;++i)
		{
			int w=ASK(u,v,i);
			if(w==i&&w!=u&&w!=v)z.push_back(i),Z.push_back(i);
			else if(w==0)Z.push_back(i);
			if(w==u)++va;
			if(w==v)++vb;
		}
		int op=-1;
		if(n-va<=n/2)op=u;
		if(n-vb<=n/2)op=v;
		if(op!=-1)
		{
			if(jud(op))return op;
			continue;
		}
		int sA=vb,sB=va; 
//		cerr<<"START\n";
		while(z.size()>1)
		{
//			cerr<<u<<" "<<v<<" "<<Z.size()<<" "<<z.size()<<endl;
//			assert(Z.size());
			vector<int>A,B;
			int x=Z[rnd()%Z.size()],y=-1;
			for(int k:z)if(ASK(u,k,x)==k)
				if(y==-1||ASK(u,k,y)==y)y=k;
//			cerr<<"MEET: "<<x<<"->"<<y<<endl;
int C=0;
			for(int i:Z)
			{
				int o1=ASK(u,y,i)==y,o2=ASK(y,v,i)==y;
				if(o1&&!o2)A.push_back(i);
				if(o2&&!o1)B.push_back(i);
				if(o1&&o2)++C;
			}
			if(sA+A.size()<=n/2&&sB+B.size()<=n/2)
			{
//				cerr<<"SELECT: "<<y<<" : "<<u<<"~"<<v<<endl;
//				cerr<<"DIV: "<<sA<<" "<<A.size()<<"  "<<sB<<" "<<B.size()<<"  "<<C<<endl;
				if(jud(y))return ans=max(ans,W),y;
				else {z.clear();break;}
			}
			if(sA+A.size()>B.size()+sB)
			{
				Z=A;int r=-1;sB+=B.size()+C;u=x;
			}
			else
			{
				Z=B;int r=-1;sA+=A.size()+C;v=x;
			}
			vector<int>xx;sort(Z.begin(),Z.end());Z.push_back(100000000);
			for(int k:z)if(*lower_bound(Z.begin(),Z.end(),k)==k)
				xx.push_back(k);z=xx,Z.pop_back(); 
//			cerr<<"ED: "<<Z.size()<<" "<<z.size()<<endl;
		}
		for(int u:z)
			if(jud(u))
			{
				ans=max(ans,W);
				return u;
			}
	}
}
int special()
{
	int u=1,v=2;
	for(int i=3;i<=n;++i)
	{
		int w=ask(u,v,i);
		if(w==i);
		else if(w==u)u=i;
		else if(w==v)v=i;
	}
	vector<int>Z;
	for(int i=1;i<=n;++i)Z.push_back(i);
	auto cmp=[&](int x,int y){return ask(x,y,v)==y;};
	nth_element(Z.begin(),Z.begin()+n/2,Z.end(),cmp);
	int y=-1;
	for(int i=n/2;i<n;++i)if(y==-1||cmp(Z[i],y))y=Z[i];
	return y;
}
int centroid(int id,int N,int M)
{
	n=N;
	if(id==1)return ask(1,2,3);
	if(id==5)return special();
	cerr<<"TESTCASE "<<ans<<endl;
	 ::M.clear();
	return solve();
}

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