#include”path.h"
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+10;
int n,m,L,R,szl,szr,wc;
int bel[N],p[N];
vector<int> link,ctr;
mt19937 rnd(time(0));

int ask(int a,int b,int c)
{
	return 0;
}

int rand(int l,int r)
{
	return rnd()%(r-l+1)+l;
}

int get_fa(int u)
{
	if(bel[u]==u) return u;
	int fa=0;
	for(auto x:link)
	{
		if(!fa) fa=x;
		else fa=ask(fa,u,x);
	}
	return fa;
} 

bool check(int x,int lc,int rc)
{
	int cnt=0,now=0;
	if(lc!=rc) cnt=abs(lc-rc),now=lc>rc?L:R;
	for(auto u:ctr)
	{
		if(u==x||bel[u]!=-1) continue;
		if(!now||ask(now,x,u)!=x) now=(!now)?u:now,cnt++;
		else if((--cnt)==0) now=0;
	}
	if(!now||now==L||now==R) return true;
	cnt=0;
	for(auto u:ctr) 
	{
		if(u==x||bel[u]!=-1) continue;
		if(u==now||ask(now,x,u)!=x) cnt++;
	}
	return cnt*2<=n;
}

int solve()
{
	if(L==R||ctr.size()==0) return 0;
	vector<int> vec;vec=ctr;
	ctr.clear(),link.clear();
	for(auto x:vec)
	{
		if(x==L||x==R) continue;
		bel[x]=ask(L,x,R);
		if(bel[x]==L) szl++;
		else if(bel[x]==R) szr++;
		else if(bel[x]==x) link.push_back(x),ctr.push_back(x);
		else ctr.push_back(x); 
	} 
	if(szl*2>n||szr*2>n) return 0;
	int nw=get_fa(ctr[rand(0,ctr.size()-1)]);
	int lc=szl,rc=szr;
	for(auto x:ctr)
	{
		if(x==nw) continue;
		if(ask(x,L,nw)!=nw) bel[x]=0,lc++;
		else if(ask(x,R,nw)!=nw) bel[x]=1,rc++;
		else bel[x]=-1;  	
	} 
	if(lc*2<=n&&rc*2<=n&&check(nw,lc,rc)) return nw;
	if(lc>rc) R=nw,szr++;
	else L=nw,szl++;
	return solve(); 
}

int centroid(int id,int N,int M)
{
	n=N,m=M;
	if(id==5)
	{
		int a=1,b=2;
		p[1]=1,p[2]=2;
		for(int i=3;i<=n;i++)
		{	
			p[i]=i;
			int mid=ask(a,b,i);
			if(mid==a) a=i;
			else if(mid==b) b=i;
		}
		nth_element(p+1,p+n/2+1,p+n+1,[=](const int&x,const int&y){return ask(a,x,y)!=x;});
		return p[n/2+1];
	}
	if(n==3) return ask(1,2,3);
	while(true)
	{
		link.clear();
		L=rand(1,n),R=rand(1,n);
		for(int u=1;u<=n;u++) 
		{
			if(u!=L&&u!=R) ctr.push_back(u);
		}
		szl=szr=1;
		if((wc=solve())) return wc;
	}
}

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:1:2: error: extended character ” is not valid in an identifier
    1 | #include”path.h"
      |  ^
answer.code:1:2: error: invalid preprocessing directive #include\U0000201dpath
    1 | #include”path.h"
      |  ^~~~~~~~~~~~
answer.code:1:16: warning: missing terminating " character
    1 | #include”path.h"
      |                ^
answer.code:7:13: error: ‘std::vector<int> link’ redeclared as different kind of entity
    7 | vector<int> link,ctr;
      |             ^~~~
In file included from /usr/include/c++/13/bits/atomic_wait.h:44,
                 from /usr/include/c++/13/bits/atomic_base.h:42,
                 from /usr/include/c++/13/bits/shared_ptr_atomic.h:33,
                 from /usr/include/c++/13/memory:81,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:56,
                 from answer.code:2:
/usr/include/unistd.h:789:12: note: previous declaration ‘int link(const char*, const char*)’
  789 | extern int link (const char *__from, const char *__to)
      |            ^~~~
answer.code: In function ‘int get_fa(int)’:
answer.code:24:20: error: ‘begin’ was not declared in this scope
   24 |         for(auto x:link)
      |                    ^~~~
answer.code:24:20: note: suggested alternatives:
In file included from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:166:
/usr/include/c++/13/valarray:1232:5: note:   ‘std::begin’
 1232 |     begin(const valarray<_Tp>& __va) noexcept
      |     ^~~~~
In file included from /usr/include/c++/13/bits/ranges_algobase.h:38,
                 from /usr/include/c++/13/bits/ranges_algo.h:38,
                 from /usr/include/c++/13/algorithm:63,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:51:
/usr/include/c++/13/bits/ranges_base.h:489:44: note:   ‘std::ranges::__cust::begin’
  489 |     inline constexpr __cust_access::_Begin begin{};
      |                                            ^~~~~
In file included from /usr/include/c++/13/filesystem:50,
                 from /usr/include/x86_64-linux-gnu/c++/13/bits/stdc++.h:200:
/usr/include/c++/13/bits/fs_dir.h:607:3: note:   ‘std::filesystem::__cxx11::begin’
  607 |   begin(recursive_directory_iterator __iter) noexcept
      |   ^~~~~
In file included from /usr/include/c++/13/bits/stl_iterator_base_types.h:71,
                 from /usr/include/c++/13/bits/stl_algobase.h:65,
                 from /usr/include/c++/13/algorithm:60:
/usr/include/c++/13/bits/iterator_concepts.h:969:10: note:   ‘std::ranges::__cust_access::begin’
  969 |     void begin(const auto&) = delete;
      |          ^~~~~
answer.code:24:20: error: ‘end’ was not declared in this scope
   24 |         for(auto x:link)
      |                    ^~~~
answer.code:24:20: note: suggested alternatives:
/usr/include/c++/13/valarray:1259:5: note:   ‘std::end’
 1259 |     end(const valarray<_Tp>& __va) noexcept
      |     ^~~
/usr/include/c++/13/bits/ranges_base.h:490:42: note:   ‘std::ranges::__cust::end’
  490 |     inline constexpr __cust_access::_End end{};
      |                                          ^~~
/usr/include/c++/13/bits/fs_dir.h:612:3: note:   ‘std::filesystem::__cxx11::end’
  612 |   end(recursive_directory_iterator) noexcept
      |   ^~~
/usr/include/c++/13/bits/ranges_base.h:137:10: note:   ‘std::ranges::__cust_access::end’
  137 |     void end(const auto&) = delete;
      |          ^~~
answer.code: In function ‘int solve()’:
answer.code:56:26: error: request for member ‘clear’ in ‘link’, which is of non-class type ‘int(const char*, const char*) noexcept’
   56 |         ctr.clear(),link.clear();
      |                          ^~~~~
answer.code:63:41: error: request for member ‘push_back’ in ‘link’, which is of non-class type ‘int(const char*, const char*) noexcept’
   63 |                 else if(bel[x]==x) link.push_back(x),ctr.push_back(x);
      |                                         ^~~~~~~~~
answer.code: In function ‘int centroid(int, int, int)’:
answer.code:102:22: error: request for member ‘clear’ in ‘link’, which is of non-class type ‘int(const char*, const char*) noexcept’
  102 |                 link.clear();
      |                      ^~~~~