#include<bits/stdc++.h>
using namespace std;
template<class T1,class T2> bool cmax(T1& a,const T2& b){return a<b?a=b,1:0;}
template<class T1,class T2> bool cmin(T1& a,const T2& b){return b<a?a=b,1:0;}
#define fir(i,x,y,...) for(int i(x),##__VA_ARGS__;i<=(y);i++)
#define firr(i,x,y,...) for(int i(x),##__VA_ARGS__;i>=(y);i--)
#define fird(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i<=(y);i+=(d))
#define firrd(i,x,y,d,...) for(int i(x),##__VA_ARGS__;i>=(y);i-=(d))
#define Yes cout<<"Yes\n"
#define No cout<<"No\n"
#define YES cout<<"YES\n"
#define NO cout<<"NO\n"
#define endl "\n"
#define ll long long
#define ull unsigned long long
extern "C" int ask(int x,int y,int z);
const int N=50005;
int x,y;
mt19937 myrnd(time(0));
bool cmp(int p,int q)
{
    if(p==q) return 0;
    return ask(p,q,x)==q;
}
vector<int> v,lnk,btw;
int bel[N],cnt1,cnt2,siz,n;
int find(int p)
{
    if(bel[p]==p) return p;
    int siz=lnk.size()-1,res=0;
    fir(i,0,siz)
    {
        if(!res) res=lnk[i];
        else res=ask(res,lnk[i],p);
    }
    return res;
}
bool check(int p,int sum1,int sum2)
{
    int cnt=abs(sum1-sum2),pos=(sum1==sum2?0:(sum1>sum2?x:y));
    fir(i,0,siz) if(!bel[i])
    {
        if(!pos||ask(pos,btw[i],p)!=p) cnt++,pos=(pos?pos:btw[i]);
        else cnt--;
        if(!cnt) pos=0;
    }
    if(!pos||pos==x||pos==y) return 1;
    cnt=0;
    fir(i,0,siz) if(!bel[i]) cnt+=(ask(pos,p,btw[i])!=p);
    return cnt*2<=n;
}
int solve()
{
    siz=v.size()-1;
    fir(i,0,siz)
    {
        if(x==v[i]||y==v[i]) continue;
        int z=ask(x,y,v[i]);
        bel[v[i]]=z;
        if(z==x) cnt1++;
        else if(z==y) cnt2++;
        else btw.push_back(v[i]),(z==v[i]?lnk.push_back(v[i]):void());
    }
    if(max(cnt1,cnt2)*2>n) return 0;
    int mid=find(btw[myrnd()%btw.size()]);
    int sum1=cnt1,sum2=cnt2;
    fir(i,0,siz)
    {
        if(btw[i]==mid) continue;
        if(ask(x,mid,btw[i])!=mid) sum1++,bel[btw[i]]=1;
        else if(ask(y,mid,btw[i])!=mid) sum2++,bel[btw[i]]=2;
        else bel[btw[i]]=0;
    }
    if(max(sum1,sum2)*2<=n&&check(mid,sum1,sum2)) return mid;
    if(sum1>sum2) y=mid,cnt2++;
    else x=mid,cnt1++;
    swap(v,btw);
    lnk.clear(),btw.clear();
    return solve();
}
extern "C" int centroid(int id,int N,int M)
{
    n=N;
    v.clear();
    if(id==1) return ask(1,2,3);
    if(id==3||id==5)
    {
        x=1,y=2;
        fir(i,3,n)
        {
            int z=ask(x,y,i);
            if(z==i) continue;
            if(z==x) x=i;
            else if(z==y) y=i;
        }
        fir(i,1,n) if(i!=x&&i!=y) v.push_back(i);
        nth_element(v.begin(),v.begin()+v.size()/2,v.end(),cmp);
        return v[v.size()/2];
    }
    while(1)
    {
        cnt1=cnt2=1;
        v.clear(),lnk.clear(),btw.clear();
        x=myrnd()%n+1,y=myrnd()%n+1;
        while(x==y) x=myrnd()%n+1,y=myrnd()%y+1;
        fir(i,1,n) if(i!=x&&i!=y) v.push_back(i);
        int G=solve();
        if(G) return G;
    }
}

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);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
/usr/bin/ld: /tmp/ccg8q0Fa.o: in function `main':
implementer.cpp:(.text.startup+0x270): undefined reference to `centroid(int, int, int)'
/usr/bin/ld: /tmp/ccjCdbCb.o: in function `cmp(int, int)':
answer.code:(.text+0x12): undefined reference to `ask'
/usr/bin/ld: /tmp/ccjCdbCb.o: in function `find(int)':
answer.code:(.text+0x93): undefined reference to `ask'
/usr/bin/ld: /tmp/ccjCdbCb.o: in function `check(int, int, int)':
answer.code:(.text+0x146): undefined reference to `ask'
/usr/bin/ld: answer.code:(.text+0x1c5): undefined reference to `ask'
/usr/bin/ld: /tmp/ccjCdbCb.o: in function `solve()':
answer.code:(.text+0x2be): undefined reference to `ask'
/usr/bin/ld: /tmp/ccjCdbCb.o:answer.code:(.text+0x3b1): more undefined references to `ask' follow
collect2: error: ld returned 1 exit status