#include<bits/stdc++.h>
#include "path.h"
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define pb push_back
using namespace std;
mt19937 rd(time(0));
const int N=1e5+5;
int n,tot,u,v,szu,szv,t[N];
vector<int> vec,nv,chn;
struct nd{
	int x;
	bool friend operator <(nd a,nd b){
		if(a.x==tot) return 1;
		if(b.x==tot) return 0;
		return ask(tot,a.x,b.x)==a.x;
	}
}a[N];
int js(int x){
	if(t[x]==x) return x;
	int res=0;
    for(auto dq:chn) if(!res) res=dq; else res=ask(res,x,dq);
	return res;
}
int chk(int p,int x1,int x2){
	int c=max(x1,x2),dq=(x1>x2?u:v);
	for(auto x:nv) if(x!=p&&!t[x]){
		if(!dq||ask(p,dq,x)!=p) dq=(!dq?x:dq),c++;
		else if(!--c) dq=0;
	}
	if(!dq||dq==u||dq==v) return 1;
	c=0;
	for(auto x:nv) if(x!=p&&!t[x]) c+=(x==dq||ask(p,dq,x)!=p);
	return (c*2<=n);
}
int solve(){
	if(u==v||vec.empty()) return 0;
	chn.clear(),nv.clear();
	for(auto 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.pb(x),nv.pb(x);
		else nv.pb(x);
	}
	if(szu*2>n||szv*2>n) return 0;
	int p=js(nv[rd()%nv.size()]),x1=szu,x2=szv;
	for(auto x:nv){
		if(ask(x,u,p)!=p) x1++,t[x]=1;
		else if(ask(x,v,p)!=p) x2++,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;
        rep(i,3,n){
			int w=ask(u,v,i);
			if(v==w) v=i; else if(u==w) u=i;
		}
        rep(i,1,n) a[i].x=i;
		nth_element(a+1,a+(n+1)/2,a+1+n);
		return a[(n+1)/2].x;
	}
	while(1){
		u=rd()%n+1,v=rd()%n+1;
		while(u==v) u=rd()%n+1,v=rd()%n+1;
		vec.clear(),nv.clear(),chn.clear();
		rep(i,1,n) if(i!=u&&i!=v) vec.pb(i);
		szu=szv=1; int c=sol();
		if(c) return c;
	}
}

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 centroid(int, int, int)’:
answer.code:75:34: error: ‘sol’ was not declared in this scope
   75 |                 szu=szv=1; int c=sol();
      |                                  ^~~