#include<bits/stdc++.h>
#include"path.h"
using namespace std;
mt19937 rnd(0xb6e0);
int 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=chn[y];else res=ash(res,x,y);
	return res;
}
int chk(int p,int x1,int x2){
	int c=max(x1,x2),gp=(x1>x2?x:y);
	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){
	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!=x&&i!=y)vec.push_back(i);
		szu=szv=1;int c=solve();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 getc(int)’:
answer.code:18:51: error: ‘ash’ was not declared in this scope; did you mean ‘ask’?
   18 |         for(int y:chn)if(!res)res=chn[y];else res=ash(res,x,y);
      |                                                   ^~~
      |                                                   ask
answer.code: In function ‘int chk(int, int, int)’:
answer.code:22:36: error: ‘x’ was not declared in this scope
   22 |         int c=max(x1,x2),gp=(x1>x2?x:y);
      |                                    ^
answer.code:22:38: error: ‘y’ was not declared in this scope
   22 |         int c=max(x1,x2),gp=(x1>x2?x:y);
      |                                      ^
answer.code:30:21: error: ‘n’ was not declared in this scope
   30 |         return c*2<=n;
      |                     ^
answer.code: In function ‘int solve()’:
answer.code:43:18: error: ‘n’ was not declared in this scope; did you mean ‘yn’?
   43 |         if(szu*2>n||szv*2>n)return -1;
      |                  ^
      |                  yn
answer.code:50:18: error: ‘n’ was not declared in this scope
   50 |         if(x1*2<=n&&x2*2<=n&&chk(p,x1,x2))return p;
      |                  ^
answer.code: In function ‘int centroid(int, int, int)’:
answer.code:71:44: error: ‘x’ was not declared in this scope
   71 |                 for(int i=1;i<=n;i++)if(i!=x&&i!=y)vec.push_back(i);
      |                                            ^
answer.code:71:50: error: ‘y’ was not declared in this scope
   71 |                 for(int i=1;i<=n;i++)if(i!=x&&i!=y)vec.push_back(i);
      |                                                  ^