#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,x,a.x)==x;
	}
}a[N];
int js(int x){
	if(t[x]==x) return x;
	int res=0;
    for(auto dq: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),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[rnd()%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 ‘bool operator<(nd, nd)’:
answer.code:15:32: error: invalid use of non-static data member ‘nd::x’
   15 |                 return ask(tot,x,a.x)==x;
      |                                ^
answer.code:11:13: note: declared here
   11 |         int x;
      |             ^
answer.code:15:40: error: invalid use of non-static data member ‘nd::x’
   15 |                 return ask(tot,x,a.x)==x;
      |                                        ^
answer.code:11:13: note: declared here
   11 |         int x;
      |             ^
answer.code: In function ‘int js(int)’:
answer.code:21:35: error: ‘y’ was not declared in this scope
   21 |     for(auto dq:chn) if(!res) res=y; else res=ask(res,x,y);
      |                                   ^
answer.code:21:57: error: ‘y’ was not declared in this scope
   21 |     for(auto dq:chn) if(!res) res=y; else res=ask(res,x,y);
      |                                                         ^
answer.code: In function ‘int solve()’:
answer.code:46:21: error: ‘rnd’ was not declared in this scope; did you mean ‘rd’?
   46 |         int p=js(nv[rnd()%nv.size()]),x1=szu,x2=szv;
      |                     ^~~
      |                     rd
answer.code:48:35: error: ‘x1’ was not declared in this scope; did you mean ‘x’?
   48 |                 if(ask(x,u,p)!=p) x1++,t[x]=1;
      |                                   ^~
      |                                   x
answer.code:49:40: error: ‘x2’ was not declared in this scope; did you mean ‘x’?
   49 |                 else if(ask(x,v,p)!=p) x2++,t[x]=2;
      |                                        ^~
      |                                        x
answer.code:52:12: error: ‘x1’ was not declared in this scope; did you mean ‘y1’?
   52 |         if(x1*2<=n&&x2*2<=n&&chk(p,x1,x2)) return p;
      |            ^~
      |            y1
answer.code:52:21: error: ‘x2’ was not declared in this scope
   52 |         if(x1*2<=n&&x2*2<=n&&chk(p,x1,x2)) return p;
      |                     ^~
answer.code:53:12: error: ‘x1’ was not declared in this scope; did you mean ‘y1’?
   53 |         if(x1>x2) v=p,szv++;
      |            ^~
      |            y1
answer.code:53:15: error: ‘x2’ was not declared in this scope
   53 |         if(x1>x2) v=p,szv++;
      |               ^~
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();
      |                                  ^~~