#include"path.h"
#include<bits/stdc++.h>
using namespace std;
#define N 100005
int n,siz[N],mx[N],vis[N];
vector<int> e[N],fat[N];
inline void dfs(int x){
	for(auto v:e[x])
		dfs(v),siz[x]+=siz[v],mx[x]=max(mx[x],siz[v]);
	mx[x]=max(mx[x],n-siz[x]);
}
inline int solve(vector<pair<int,int>> vec){
	if(vec.size()==1) return vec[0].first;
	if(vec.size()==2) return vec[0].second>vec[1].second?vec[0].first:vec[1].first;
	for(auto tmp:vec) siz[tmp.first]=tmp.second,mx[tmp.first]=0;
	int r=vec[0].first;
	for(int i=1;i<vec.size();i++)
		for(int j=i+1;j<vec.size();j++){
			int x=vec[i].first,y=vec[j].first,res=ask(r,x,y);
			if(res==x) fat[y].emplace_back(x);
			if(res==y) fat[x].emplace_back(y);
		}
	for(int i=1;i<vec.size();i++) fat[vec[i].first].emplace_back(r);
	for(int i=1;i<vec.size();i++){
		int x=vec[i].first;
		for(auto tmp:vec) vis[tmp.first]=0;
		for(auto tmp:fat[x]) vis[tmp]=1;
		int num=0;
		for(int j=0;j<vec.size();j++){
			int y=vec[j].first;
			if(vis[y]&&fat[y].size()+1==fat[x].size()) num++,e[y].emplace_back(x);
		}
		assert(num>=1);
	}
	dfs(r);
	int rt=0;
	for(auto tmp:vec){
		int v=tmp.first;
		if(!rt||mx[v]<mx[rt]) rt=v;
	}
	for(auto tmp:vec){
		int v=tmp.first;
		fat[v].clear(),e[v].clear(),siz[v]=mx[v]=0;
	}
	return rt;
}
mt19937 rng(1);
inline int rd(int l,int r){
	return rng()%(r-l+1)+l;
}
namespace Chain{
	int val[N];
	inline int calc(vector<pair<int,int>> vec){
		if(vec.size()<=10) return solve(vec);
		for(auto tmp:vec) val[tmp.first]=tmp.second;
		int k=rd(0,vec.size()-1),pos=rd(0,vec.size()-1);
		while(val[vec[k].first]>1||k==pos) k=rd(0,vec.size()-1),pos=rd(0,vec.size()-1);
		k=vec[k].first,pos=vec[pos].first;
		assert(val[k]==1);
		vector<pair<int,int>> L,R;
		int lsum=0,rsum=0;
		L.emplace_back(pos,val[pos]),lsum+=val[pos];
		for(auto tmp:vec){
			int x=tmp.first;
			if(x==k||x==pos) continue;
			if(ask(k,pos,x)==k){
				R.emplace_back(x,val[x]),rsum+=val[x];
			}else{
				L.emplace_back(x,val[x]),lsum+=val[x];
			}
		}
		if(lsum==rsum) return k;
		if(lsum<rsum) swap(lsum,rsum),swap(L,R);
		L.emplace_back(k,1+rsum);
		for(auto tmp:vec) val[tmp.first]=0;
		return calc(L);
	}
	inline int solve(int n){
		vector<pair<int,int>> vec;
		for(int i=1;i<=n;i++) vec.emplace_back(i,1);
		return calc(vec);
	}
}
namespace All{
	int val[N],used[N],sum[32],app[N];
	vector<pair<int,int>> son[32];
	inline int calc(vector<pair<int,int>> vec){
		if(vec.size()<=30) return solve(vec);
		for(auto tmp:vec) val[tmp.first]=tmp.second;
		int x=rd(0,vec.size()-1),y=rd(0,vec.size()-1),k=-1;
		while(x==y) x=rd(0,vec.size()-1),y=rd(0,vec.size()-1);
		for(auto tmp:vec){
			int v=tmp.first,r=ask(x,y,v);
			if(!r) continue;
			k=r;
			break;			
		}
		vector<int> pos;
		for(int i=0;i<vec.size();i++)
			if(vec[i].first!=k) pos.emplace_back(vec[i].first);
		shuffle(pos.begin(),pos.end(),rng);
		used[k]=1;
		int tot=0;
		for(int i=0;i<30;i++){
			app[i]=-1;
			for(int j=0;j<i;j++){
				if(ask(pos[i],pos[j],k)!=k){
					app[i]=app[j];
					break;
				}
			}
			if(app[i]==-1){
				tot++,son[tot].clear(),sum[tot]=0;
				app[i]=tot;
			}
			son[app[i]].emplace_back(pos[i],val[pos[i]]),sum[app[i]]+=val[pos[i]],used[pos[i]]=1;
		}
		int els=0;
		for(auto tmp:vec){
			int x=tmp.first;
			if(used[x]) continue;
			bool flag=0;
			for(int i=1;i<=tot;i++){
				if(ask(k,x,son[i][0].first)!=k){
					son[i].emplace_back(x,val[x]),sum[i]+=val[x];
					flag=1;
					break;
				}
			}
			if(!flag) els+=val[x];
		}
		int p=0;
		for(int i=1;i<=tot;i++) 
			if(!p||sum[i]>sum[p]) p=i;
		for(auto tmp:vec) used[tmp.first]=0;
		if(sum[p]<=n/2) return k;
		for(int i=1;i<=tot;i++)
			if(i!=p) els+=sum[i];
		son[p].emplace_back(k,val[k]+els);
		return calc(son[p]);
	}
	inline int solve(int n){
		vector<pair<int,int>> vec;
		for(int i=1;i<=n;i++) vec.emplace_back(i,1);
		return calc(vec);
	}
}
int centroid(int id,int _n,int m){
	n=_n;
	if(id==1) return ask(1,2,3);
	if(id==2){
		vector<pair<int,int>> vec;
		for(int i=1;i<=n;i++) vec.emplace_back(i,1);
		return solve(vec);
	}
	if(id==3||id==5) return Chain::solve(n);
	return All::solve(n);
}