#include"path.h"
#include<bits/stdc++.h>
using namespace std;
const int N=1e5+50;

mt19937 rad(time(0));

int n,m;
vector<int>s;

void clear()
{
	s.clear();
}

int rd(int l,int r)
{
	return rad()%(r-l+1)+l;
}

int chk(int x)
{
	int now=0,cnt=0;
	for(int i=1;i<=n;i++)if(i!=x)
	{
		if(!cnt)
		{
			now=i,cnt=1;
			continue;
		}
		if(ask(x,i,now)==x)cnt--;
		else cnt++;
	}
	cnt=1;
	for(int i=1;i<=n;i++)if(i!=x&&i!=now)cnt+=ask(x,i,now)!=x;
	return cnt<=m;
}

int sol(int u,int v)
{
	if(s.empty())return 0;
	int t=rd(0,s.size()-1),pos=s[t];
	int cl=0,cr=0,c=0;
	for(int i=1;i<=n;i++)if(i!=pos)
	{
		if(i==u){++cl;continue;}
		if(i==v){++cr;continue;}
		int w;
		w=ask(u,pos,i);
		if(w==u||w==i||w==0){++cl;continue;}
		w=ask(v,pos,i);
		if(w==v||w==i||w==0){++cr;continue;}
		++c;
	}
	if(max(cl,max(cr,c))<=m)return pos;
	if(max(cl,cr)<=m)return chk(pos);
	vector<int>L,R;
	if(pos!=u)L.push_back(u);
	if(pos!=v)R.push_back(v);
	for(auto x:s)if(x!=pos&&x!=u&&x!=v)
	{
		int w=ask(u,x,pos);
		if(w==x)L.push_back(x);
		else R.push_back(x);
	}
	if(cl>cr){swap(L,s);return sol(u,pos);}
	swap(R,s);return sol(pos,v);
}

int solve(int u,int v)
{
	if(u==v)return 0;
	for(int i=1;i<=n;i++)if(ask(u,v,i)==i)s.push_back(i);
	return sol(u,v);
}

int centroid(int id,int N,int M)
{
	n=N;m=n/2;int ans=0;
	// for(int i=1;i<=n;i++)if(chk(i))return i;
	while(!(ans=solve(rd(1,n),rd(1,n))))clear();
	return ans;
}