//#include "path.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
const int NN=2.5e5+5;
int n,res[NN],a[NN];
vector<int> oth,path,g;
//mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int fid(int x){
	if(res[x]==x) return x;
	int ret=0;
	for(int y:path){
		if(!ret) ret=y;
		else ret=ask(x,y,ret);
	}
	return ret;
}
int u,v;
bool check(int x,int c1,int c2){
	int cnt=abs(c1-c2),nw=0;
	if (c1!=c2) nw=c1>c2?u:v;
	for (int y:oth)
		if (x!=y&&res[y]==-1){
			if (!nw||ask(nw,x,y)!=x) {
				if (!nw) nw=y;
				cnt++;
			}
			else if (!(--cnt))
				nw=0;
		}
	if (!nw||nw==u||nw==v) return 1;
	cnt=0;
	for (int y:oth)
		if (x!=y&&res[y]==-1&&(nw==y||ask(nw,x,y)!=x)) cnt++;
	return cnt<=n/2;
}
int szu,szv;
int solve(){
	if(u==v||oth.empty()) return 0;
	g.clear();
	for(int x:oth) g.pb(x);
	oth.clear(),path.clear();
	for(int x:g){
		if(x==u||x==v) continue;
		res[x]=ask(u,v,x);
		if(res[x]==u) ++szu;
		else if(res[x]==v) ++szv;
		else if(res[x]==x) oth.pb(x),path.pb(x);
		else oth.pb(x);
	}
	if(szu>n/2||szv>n/2) return 0;
	int fa=fid(oth[rand()%oth.size()]);
	int ucnt=szu,vcnt=szv;
	for(int x:oth){
		if(x==fa) continue;
		if(ask(u,x,fa)!=fa)++ucnt,res[x]=0;
		else if(ask(v,x,fa)!=fa) ++vcnt,res[x]=1;
		else res[x]=-1;
	}
	if(ucnt<=n/2&&vcnt<=n/2&&check(fa,ucnt,vcnt)) return fa;
	if(ucnt>vcnt) v=fa,szv++;
	else u=fa,szu++;
	return solve();
}
int centroid(int id, int N, int M){
	srand(time(0));
	n=N;
	if(id==1){
		return ask(1,2,3);
	}
	if(id==3||id==5){
		u=1,v=2;
		for(int i=3;i<=n;++i){
			int w=ask(u,v,i);
			if(w==u) u=i;
			else if(w==v) v=i;
		}
		for(int i=1;i<=n;++i) a[i]=i;
		nth_element(a+1,a+n/2+1,a+n+1,[=](int x,int y){return ask(u, x, y)==x;});
		return a[n/2+1];
	}
	while("HBH IS AKING IOI |a|<|o|"){
		oth.clear();
		u=rand()%n+1,v=rand()%n+1;szu=szv=1;
		for(int i=1;i<=n;++i) if(i!=u&&i!=v) oth.pb(i);
		int ret=solve();
		if(ret) return ret;
	}
}

implementer.cpp: In function ‘int main()’:
implementer.cpp:60:14: warning: ignoring return value of ‘size_t fread(void*, size_t, size_t, FILE*)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   60 |         fread(Interactor::rbuf,1,50000000,stdin);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
answer.code: In function ‘int fid(int)’:
answer.code:14:26: error: ‘ask’ was not declared in this scope
   14 |                 else ret=ask(x,y,ret);
      |                          ^~~
answer.code: In function ‘bool check(int, int, int)’:
answer.code:24:34: error: ‘ask’ was not declared in this scope
   24 |                         if (!nw||ask(nw,x,y)!=x) {
      |                                  ^~~
answer.code:34:47: error: ‘ask’ was not declared in this scope
   34 |                 if (x!=y&&res[y]==-1&&(nw==y||ask(nw,x,y)!=x)) cnt++;
      |                                               ^~~
answer.code: In function ‘int solve()’:
answer.code:45:24: error: ‘ask’ was not declared in this scope
   45 |                 res[x]=ask(u,v,x);
      |                        ^~~
answer.code:56:20: error: ‘ask’ was not declared in this scope
   56 |                 if(ask(u,x,fa)!=fa)++ucnt,res[x]=0;
      |                    ^~~
answer.code: In function ‘int centroid(int, int, int)’:
answer.code:69:24: error: ‘ask’ was not declared in this scope
   69 |                 return ask(1,2,3);
      |                        ^~~
answer.code:74:31: error: ‘ask’ was not declared in this scope
   74 |                         int w=ask(u,v,i);
      |                               ^~~
answer.code: In lambda function:
answer.code:79:71: error: ‘ask’ was not declared in this scope
   79 |                 nth_element(a+1,a+n/2+1,a+n+1,[=](int x,int y){return ask(u, x, y)==x;});
      |                                                                       ^~~