#include"path.h"
#include<bits/stdc++.h>
using namespace std;
mt19937 rnd(19260817);
int n,m,vis[50005],num[50005];
int solve(vector<int>g,int dep)
{
	if(dep>=30)
	{
		for(int i=1;i<=n*50;i++)
		{
			int x=rnd()%n+1,y=rnd()%n+1,z=rnd()%n+1;
			while(x==y||y==z||x==z)x=rnd()%n+1,y=rnd()%n+1,z=rnd()%n+1;
			int now=ask(x,y,z);
			if(now!=0)num[now]++;
		}
		int pos=0;
		for(int i=1;i<=n;i++)if(num[i]>num[pos])pos=i;
		for(int i=1;i<=n;i++)num[i]=0;cerr<<pos<<'\n';
		return pos;
	}
	//for(int i=0;i<g.size();i++)cout<<g[i]<<' ';cout<<'\n';
	if(g.size()==1)return g[0];
	shuffle(g.begin(),g.end(),rnd);
	for(int i=0;i<g.size();i++)vis[g[i]]=1;
	int x=g[0],y=g[1],val0=0,val1=0;
	vector<int>tmp0,tmp1,tmp2;
	for(int i=1;i<=n;i++)
	{
		if(i==x||i==y)continue;
		int now=ask(x,y,i);
		if(now==x)
		{
			if(vis[i])tmp0.emplace_back(i);
			val0++;
		}
		else if(now==y)
		{
			if(vis[i])tmp1.emplace_back(i);
			val1++;
		}
		else 
		{
			if(vis[i])tmp2.emplace_back(i);
		}
	}
	//cout<<x<<' '<<y<<' '<<val0<<' '<<val1<<'\n';
	for(int i=0;i<g.size();i++)vis[g[i]]=0;
	tmp0.emplace_back(x);tmp1.emplace_back(y);
	if(val0==n/2)return x;
	if(val1==n/2)return y;
	if(val0>n/2)return solve(tmp0,dep+1);
	else if(val1>n/2)return solve(tmp1,dep+1);
	else return solve(tmp2,dep+1);
}
int centroid(int id,int N,int M)
{
	vector<int>g;n=N;m=M;
	for(int i=1;i<=n;i++)g.emplace_back(i);
	return solve(g,1); 
}