#include<bits/stdc++.h>
#include "soul.h"
using namespace std;
// struct node
// {
// 	size_t operator()(const array<int,3>&a)const
// 	{
// 		return (a[0]*1000000007u^a[1]*998244353u^a[2]*1000000009u);
// 	}
// };
// unordered_map<array<int,3>,int,node>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;
mt19937 rnd(43525);
inline vector<int>get_line(int u,int v,const vector<int>&up)
{
	// cerr<<"DIV: "<<up.size()<<" "<<u<<" "<<v<<endl;
	if(u==v)return {u};
	if(up.size()==2)return {u,v};
	int x;
	do x=up[rnd()%up.size()];while(x==u||x==v);
	vector<int>A,B;
	for(int k:up)
	{
		int w1=ASK(k,x,u);
		int op=-1;
		if(w1==k)A.push_back(k),op=1;
		else if(w1==x)B.push_back(k),op=0;
		#ifdef DOQ
		else cerr<<"Oops: "<<k<<" "<<x<<" "<<u<<" = "<<w1<<endl,
			assert(0);
		if(k==u)
		{
			// cerr<<"Oops: "<<k<<" "<<x<<" "<<u<<" = "<<w1<<endl;
			assert(op==1);
		}
		if(k==v)assert(op ==0);
		#endif
	}
	B.push_back(x);
	// cerr<<u<<" "<<v<<" DIV: "<<x<<endl;
	// cerr<<"  ";for(int w:B)cerr<<w<<",";cerr<<endl;
	// cerr<<"  ";for(int w:A)cerr<<w<<",";cerr<<endl;
	A=get_line(u,x,A),B=get_line(x,v,B);
	A.pop_back();
	for(int k:B)A.push_back(k);
	return A;
}
const int N=1e5+10;
int op[N],fa[N];
vector<int>po[N];
inline int solve()
{
	// assert(po[2].empty());
	vector<int>Z;
	for(int i=1;i<=n;++i)Z.push_back(i),fa[i]=op[i]=0;
	int usz=0,vsz=0;
	int u=rnd()%n+1,v=rnd()%n+1,lst_ans=-1,same_cnt=0;
	while(u==v)v=rnd()%n+1;
	while(1)
	{
		#ifdef DOQ
		cerr<<"UP_LINE: "<<u<<"~"<<v<<endl;
		#endif
			// assert(po[2].empty());
		// for(int i=1;i<=n;++i)cerr<<fa[i]<<",";cerr<<endl;
		vector<int>X,V1,V2;
		for(int k:Z)
			if(k!=u&&k!=v)
			{
				// assert(fa[k]==u||fa[k]==v);
				if(fa[k]==u){V1.push_back(k);continue;}
				else if(fa[k]==v){V2.push_back(k);continue;}
				int w=ASK(u,k,v);
				// cerr<<u<<","<<k<<","<<v<<" "<<w<<endl;
				if(w==k)X.push_back(k);
				else if(w==u)V1.push_back(k);
				else if(w==v)V2.push_back(k);
			}
		if(V1.size()<V2.size())swap(u,v),swap(V1,V2);
		// cerr<<u<<" : ";for(int k:V1)cerr<<k<<",";cerr<<endl;
		// cerr<<v<<" : ";for(int k:V2)cerr<<k<<",";cerr<<endl;
		// cerr<<"X : ";for(int k:X)cerr<<k<<",";cerr<<endl;
		if(V1.size()>=n/2)
		{
			do v=V1[rnd()%V1.size()];while(v==u);
			for(int k:V1)op[k]=1;
			for(int i=1;i<=n;++i)if(!op[i])fa[i]=u;else fa[i]=0;
			for(int k:V1)op[k]=0;
			if(lst_ans==u)++same_cnt;
			else lst_ans=u,same_cnt=0;
			#ifdef DOQ
			cerr<<"CHOOSE: "<<u<<endl;
			#endif
			// assert(po[2].empty());
			if(same_cnt>=(3+(n<=5000)*7))return u;
			continue;
		}
		// cerr<<"DIV\n";
		X.push_back(u),X.push_back(v);
		X=get_line(u,v,X);
		// cerr<<"ED: ";
		// for(int k:X)cerr<<k<<",";cerr<<endl;
		// assert(po[2].empty());
		for(int k:X)op[k]=1;//,assert(po[k].empty());
		for(int k:Z)
		{
			// cerr<<k<<": "<<fa[k]<<endl;
			if(fa[k])//assert(fa[k]==u||fa[k]==v),
				po[fa[k]].push_back(k),op[k]=0;
			else if(op[k])fa[k]=k,po[k].push_back(k),op[k]=0;
			else
			{
				int l=0,r=X.size()-1;
				while(l<r)
				{
					// cerr<<l<<" "<<r<<endl;
					int mid=l+r+1>>1,w=ASK(u,X[mid],k);
					if(w==u){l=0;break;}
					else if(w==k||w==0)r=mid-1;
					else if(w==X[mid])l=mid;
					else if(w==u)
						{l=0;break;}
						// cerr<<"Oops: "<<u<<" "<<X[mid]<<" "<<k<<" = "<<w<<endl,
						// assert(0);
				}
				// cerr<<"RESULT: "<<k<<" : "<<l<<": "<<X[l]<<endl;
				po[X[l]].push_back(k);
				fa[k]=X[l];
			}
		}
		// for(int k:X)assert(!op[k]);
		vector<int>pre(X.size()),suf(X.size());
		for(int i=0,s=0;i<X.size();++i)pre[i]=s,s+=po[X[i]].size();
		for(int i=X.size()-1,s=0;~i;--i)suf[i]=s,s+=po[X[i]].size();
		#ifdef DOQ
		cerr<<pre.back()<<","<<suf[0]<<endl;
		assert(pre.back()<n&&suf[0]<n);
		#endif
		int mn=1e9,I=0;for(int i=0;i<X.size();++i)
		{
			// cerr<<po[X[i]].size()<<" "<<pre[i]<<" "<<suf[i]<<endl;
			// assert(po[X[i]].size());
			// assert(pre[i]+suf[i]<n);
			int w=max(pre[i],suf[i]);
			if(mn>w)mn=w,I=i;
		}
		for(int i=0;i<X.size();++i)
			if(i!=I)for(int k:po[X[i]])fa[k]=X[I];
			else for(int k:po[X[i]])fa[k]=0;
		for(int i=0;i<X.size();++i)
			if(i!=I)fa[X[i]]=X[I];
			else fa[X[i]]=0;
			#ifdef DOQ
		cerr<<"MEET: "<<X[I]<<" "<<u<<" "<<v<<" "<<mn<<endl;
		#endif
		// auto ww=find(X.begin(),X.end(),599);
		// if(ww!=X.end())
		// {
		// 	cerr<<"IN TOO\n";
		// 	cerr<< pre[ww-X.begin()]<<" "<<suf[ww-X.begin()]<<endl;
		// }
		// ww=find(X.begin(),X.end(),2);
		// if(ww!=X.end())
		// {
		// 	cerr<<"IN TOO 2\n";
		// 	cerr<< pre[ww-X.begin()]<<" "<<suf[ww-X.begin()]<<endl;
		// }
		// for(int i=0;i<X.size();++i)cerr<<po[X[i]].size()<<endl;
		u=X[I];
		if(po[X[I]].size()==1)
		{
			// cerr<<"SPECIAL\n";
			for(int i=0;i<X.size();++i)po[X[i]].clear();
			return u;
		}
		do v=po[X[I]][rnd()%po[X[I]].size()];while(u==v);
		for(int i=0;i<X.size();++i)po[X[i]].clear();
		// for(int i=0;i<X.size();++i)assert(po[X[i]].empty());
		// assert(po[2].empty());
		// assert(lst_ans!=u);
		lst_ans=u;same_cnt=0;
	}
}
int centroid(int id,int N,int M)
{
	cerr<<"TESTCASE\n";
	// ::M.clear();
	n=N;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.