#include <bits/stdc++.h>
#include "soul.h"
using namespace std;
int n,u,v,szu,szv;
const int N=3e5+5;
int res[N],a[N];
vector<int>g,oth,path;
int ask(int x,int y,int z); 
int fnd(int x){
	if(res[x]==x)return x;
	int ret=0;
	for(int i=0;i<int(path.size());++i)
	if(!ret)ret=path[i];
	else ret=ask(x,path[i],ret);
	return ret;
}
bool check(int x,int ax,int bx){
	int cnt=abs(ax-bx),now=0;
	if(ax!=bx)now=ax>bx?u:v;
	for(int i=0;i<int(oth.size());++i){
		int y=oth[i];
		if(x!=y&&res[y]==-1){
			if(!now||ask(now,x,y)!=x){
				if(!now)now=y;
				++cnt;
			}
		}
	}
	if(!now||now==u||now==v)return 1;
	cnt=0;
	for(int i=0;i<int(oth.size());++i){
		int y=oth[i];
		if(x!=y&&res[y]==-1&&(now==y||ask(now,x,y)!=x))++cnt;
	}
	return cnt<=n/2;
}
int solve(){
	if(u==v||oth.empty())return 0;
	g.clear();
	for(int i=0;i<int(oth.size());++i)
	g.push_back(oth[i]);
	oth.clear();path.clear();
	for(int i=0;i<int(g.size());++i){
		int x=g[i];
		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.push_back(x),path.push_back(x);
		else oth.push_back(x); 
	}
	if(szu>n/2||szv>n/2)return 0;
	int fa=fnd(oth[rand()%oth.size()]);
	int ucnt=szu,vcnt=szv;
	for(int i=0;i<int(oth.size());++i){
		int x=oth[i];
		if(x==fa)continue;
		if(ask(u,x,fa)!=fa)res[x]=0,++ucnt;
		else if(ask(v,x,fa)!=fa)res[x]=1,++vcnt;
		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){
	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==v)v=i;
			else if(w==u)u=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(1){
		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.push_back(i);
		int nb=solve();
		if(nb)return nb;
	}
}

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:2:10: fatal error: soul.h: No such file or directory
    2 | #include "soul.h"
      |          ^~~~~~~~
compilation terminated.