#include<bits/stdc++.h>
#include "path.h"
using namespace std;
struct hsh
{
	static const unsigned long long B=1e9+7;
	unsigned long long operator()(const array<int,3>&x)const
		{return (x[0]*B+x[1])*B*x[2]+B;}
};
namespace Map
{
	const int P=5e7+7,N=1e7+10;
	hsh F;
	int hd[P],vl[N];
	unsigned long long to[N];
	int nx[N],tt;
	inline void clr()
	{
		for(int i=1;i<=tt;++i)hd[to[i]%P]=0;
		tt=0;
	}
	int mxz=0,C=0;
	inline int&get(const array<int,3>&A)
	{
		auto z=F(A); 
		int u=z%P,zz=0;
		for(int i=hd[u];i;i=nx[i],++zz)if(to[i]==z)return vl[i];
//		if(C++%1000000==0)cerr<<C<<" "<<mxz<<endl;
//		mxz=max(mxz,zz);
		to[++tt]=z,nx[tt]=hd[u],hd[u]=tt,vl[tt]=-1;return vl[tt];
	}
}
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);
	int&zz=Map::get(a);
	 if(zz!=-1)return zz;
	 return zz=ask(x,y,z);
}
int n,bn[101000];
mt19937 rnd(time(0));
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,o1[101000],o2[101000];
int solve()
{
	for(int i=1;i<=n;++i)bn[i]=0;
	int W=0;
	while(1)
	{
		++W;
		int u=rnd()%n+1,v=rnd()%n+1;
//		cerr<<u<<"~"<<v<<" ",cerr<<ask(u,v,13637)<<" ";
		if(u==v)continue;
		vector<int>z,Z;
		for(int i=1;i<=n;++i)
			if(ASK(u,v,i)==i)z.push_back(i);
		for(int i=1;i<=n;++i)Z.push_back(i);
		int sA=0,sB=0; 
//		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;
				::o1[i]=o1,::o2[i]=o2;
			}
			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;}
			}
//			cerr<<A.size()<<" "<<B.size()<<" "<<C<<"  "<<y<<endl;
			if(sA+A.size()>B.size()+sB)
			{
				Z=A;int r=-1;sB+=B.size()+C;
				for(int k:z)if(k!=y&&o1[k])
					if(r==-1||ASK(v,r,k)==r)r=k;u=r;
			}
			else
			{
				Z=B;int r=-1;sA+=A.size()+C;
				for(int k:z)if(k!=y&&o2[k])
					if(r==-1||ASK(u,r,k)==r)r=k;v=r;
			}
			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 centroid(int id,int N,int M)
{
	if(id==1)return ask(1,2,3);
	cerr<<"TESTCASE "<<ans<<endl;
	ans=0;
	Map::clr(); 
	n=N;return solve();
}