#include"path.h"
#include<bits/stdc++.h>
using namespace std;
template<typename A>
using vc=vector<A>;
using pi=pair<int,int>;
mt19937 _rand(time(0)^clock());
int ID;
inline bool check(int n,int u)
{
	if(u==-1) return false;
	int now=-1,sum=0;
	for(int i=1;i<=n;i++) if(i!=u)
	{
		if(now==-1) now=i,sum=1;
		else
		{
			int res=ask(u,i,now);
			if(res!=u) sum++;
			else
			{
				if(sum==1) now=-1,sum=0;
				else sum--;
			}
		}
	}
	if(now==-1) return true;
	int siz=0;
	for(int i=1;i<=n;i++) if(i!=u)
	{
		if(i==now) siz++;
		else if(ask(i,now,u)!=u) siz++;
	}
	return siz*2<n;
}
int tag[50001],col=0;
inline void T(vc<int>&num)
{
	col++;
	for(int i:num) tag[i]=col;
}
inline int get(int n)
{
	int x=_rand()%n+1,y=_rand()%n+1;
	while((tag[x]&&tag[y]==tag[x])||x==y) y=_rand()%n+1;

	int lsiz=1,rsiz=1;vc<int>L,N;
	for(int i=1;i<=n;i++) if(i!=x&&i!=y)
	{
		int res=ask(i,x,y);
		if(res==x) lsiz++;
		else if(res==y) rsiz++;
		else if(res==i) L.push_back(i);
		else N.push_back(i);
	}
	T(L);
	if(lsiz*2>n&&ID==8) return x;
	if(rsiz*2>n&&ID==8) return y;
	while(L.size()>1)
	{
		// printf("x=%d y=%d lsiz=%d rsiz=%d\n",x,y,lsiz,rsiz);
		// for(int i:L) printf("%d ",i);
		// putchar('\n');
		// for(int i:N) printf("%d ",i);
		// putchar('\n');
		
		shuffle(L.begin(),L.end(),_rand);
		int m1=L[0],m2=L[1],nl=lsiz,nr=rsiz,nm1=1,nm=0,nm2=1;
		if(ask(x,m1,m2)==m2) swap(m1,m2);
		vc<int>N1,N2,N3,L1,L2,L3;

		for(int i:L) if(i!=m1&&i!=m2)
		{
			int res=ask(m1,m2,i);
			if(res==i) nm++,L2.push_back(i);
			else if(res==m1) nl++,L1.push_back(i);
			else nr++,L3.push_back(i);
		}
		for(int i:N)
		{
			int res=ask(m1,m2,i);assert(res!=i);
			if(res==m1)
			{
				if(ask(i,x,m1)==m1) nm1++;
				else nl++,N1.push_back(i);
			}
			else if(res==m2)
			{
				if(ask(i,y,m2)==m2) nm2++;
				else nr++,N3.push_back(i);
			}
			else nm++,N2.push_back(i);
		}
		// printf("%d %d\n",m1,m2);
		// printf("%d %d %d %d %d\n",nl,nm1,nm,nm2,nr);

		if((nl+nm1)*2>n)
		{
			if((n-nl)*2>n)
			{
				if((n-nm1)*2>n) return m1+n;
				return m1;
			}
			rsiz=n-nl,L=L1,N=N1,y=m1;
		}
		else if((nr+nm2)*2>n)
		{
			if((n-nr)*2>n)
			{
				if((n-nm2)*2>n) return m2+n;
				return m2;
			}
			lsiz=n-nr,L=L3,N=N3,x=m2;
		}
		else
		{
			lsiz=nl+nm1,rsiz=nr+nm2;
			L=L2,N=N2,x=m1,y=m2;
		}
	}
	if(L.size()==0) return -1;
	return L[0];
}
int centroid(int id,int n,int m)
{
	ID=id;
	if(n==3) return ask(1,2,3);
	memset(tag,0,sizeof(tag));
	int u=-1;
	while(true)
	{
		u=get(n);
		if(u>n||check(n,u)) return u>n?u-n:u;
	}
}
// g++ grader.cpp path.cpp -o T3 -std=c++14 -Wl,--stack=998244353