#include<bits/stdc++.h>
#include"path.h"
using namespace std;
mt19937 rnd(0xb6e0);
int n,tops,u,v,szu,szv,t[50000];
struct Node{
	int x;
	bool operator <(const Node A){
		if(x==tops)return true;
		if(A.x==tops)return false;
		return ask(tops,x,A.x)==x;
	}
}a[50000];
vector<int> vec,nv,chn;
int getc(int x){
	if(t[x]==x)return x;
	int res=0;
	for(int y:chn)if(!res)res=y;else res=ask(res,x,y);
	return res;
}
int chk(int p,int x1,int x2){
	int c=max(x1,x2),gp=(x1>x2?u:v);
	for(int x:nv)if(x!=p&&!t[x]){
		if(!p||ask(p,gp,x)!=p)gp=(!p?x:gp),c++;
		else if(!--c)gp=0;
	}
	if(!p||p==u||p==v)return true;
	c=0;
	for(int x:nv)if(x!=p&&!t[x])c+=(t[x]==p||ask(p,gp,x)!=p);
	return c*2<=n;
}
int solve(){
	if(u==v||vec.empty())return -1;
	chn.clear();nv.clear();
	for(int x:vec)if(x!=u&&x!=v){
		int c=ask(u,v,x);
		t[x]=c;
		if(c==u)szu++;
		else if(c==v)szv++;
		else if(c==x)chn.push_back(x),nv.push_back(x);
		else nv.push_back(x);
	}
	if(szu*2>n||szv*2>n)return -1;
	int p=nv[rnd()%nv.size()],x1=szu,x2=szv;
	for(int x:nv){
		if(ask(x,u,p)!=p)szu++,t[x]=1;
		else if(ask(x,v,p)!=p)szv++,t[x]=2;
		else t[x]=0;
	}
	if(x1*2<=n&&x2*2<=n&&chk(p,x1,x2))return p;
	if(x1>x2)v=p,szv++;else u=p,szu++;swap(vec,nv);
	return solve();
}
int centroid(int id,int N,int M){
	n=N;
	if(id==1)return ask(1,2,3);
	if(id==3||id==5){
		int u=1,v=2;
		for(int i=3;i<=n;i++){
			int w=ask(u,v,i);
			if(v==w)v=i;
			else if(u==w)u=i;
		}
		for(int i=1;i<=n;i++)a[i].x=i;
		nth_element(a+1,a+(n+1)/2,a+1+n);
		return a[(n+1)/2].x;
	}
	while(true){
		u=rnd()%n+1,v=rnd()%n+1;
		while(u==v)u=rnd()%n+1,v=rnd()%n+1;
		vec.clear();nv.clear();chn.clear();
		for(int i=1;i<=n;i++)if(i!=u&&i!=v)vec.push_back(i);
		szu=szv=1;int c=solve();if(~c)return c;
	}
}