#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());
inline bool check(int n,int u)
{
	// printf("check %d %d\n",n,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;
}
inline int get(int n)
{
	int x=_rand()%n+1,y=_rand()%n+1;
	while(x==y) x=_rand()%n+1,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);
	}
	if(lsiz*2>n) return x;
	if(rsiz*2>n) return y;
	while(true)
	{
		// 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');
		assert(L.size());
		shuffle(L.begin(),L.end(),_rand);
		int m=L[0],nl=lsiz,nr=rsiz,nm=1;
		vc<int>L1,L2,N1,N2;

		for(int i:L) if(i!=m)
		{
			int res=ask(x,m,i);
			if(res==i) L1.push_back(i),nl++;
			else L2.push_back(i),nr++;
		}
		for(int i:N)
		{
			if(ask(x,m,i)==m)
			{
				if(ask(y,m,i)==m) nm++;
				else nr++,N2.push_back(i);
			}
			else nl++,N1.push_back(i);
		}
		// printf("m=%d nl=%d nr=%d nm=%d\n",m,nl,nr,nm);
		if((nl+nm)*2>n)
		{
			if((nr+nm)*2>n) return m;
			L=L1,N=N1,y=m,rsiz=nr+nm;
		}
		else
		{
			if((nr+nm)*2<n) return -1;
			L=L2,N=N2,x=m,lsiz=nl+nm;
		}
	}
}
int centroid(int id,int n,int m)
{
	int u=-1;
	while(true)
	{
		u=get(n);
		if(check(n,u)) return u;
	}
}
// g++ grader.cpp path.cpp -o T3 -std=c++14 -Wl,--stack=998244353