#include<cstdio>
#include<algorithm>
#include<vector>
#include<random>
#include<map>
#include"path.h"
namespace Solve
{
    using namespace std;
    typedef long long ll;
    const int N=1000001;
    int n,f[N],fa[N];
    bool g[N],h[N];
    vector<int> p;
    unordered_map<ll,int> Map;
    int rnd(int x,int y)
    {
        static std::mt19937 rd(std::random_device{}());
        return (std::uniform_int_distribution<int>(x,y))(rd);
    }
    int find(int x)
    {
        if(fa[x]==x) return x;
        return fa[x]=find(fa[x]);
    }
    int query(int x,int y,int z)
    {
        if(y<x) swap(x,y);
        if(z<x) swap(x,z);
        if(z<y) swap(y,z);
        ll s=(ll)(x-1)*n*n+(ll)(y-1)*n+z;
        if(Map.count(s)) return Map[s];
        else return Map[s]=ask(x,y,z);
    }
    int solve(int x1,int x2)
    {
        p.clear();
        for(int i=1;i<=n;++i) f[i]=1,g[i]=false,fa[i]=i;
        Map.clear();
        p.push_back(x1);
        p.push_back(x2);
        for(int i=1;i<=n;++i)
        {
            if(i==x1||i==x2) continue;
            if(query(x1,i,x2)==i) p.push_back(i);
        }
        static int S=0;
        while(!p.empty())
        {
            int u=rnd(1,n),x=p.front();
            for(auto j:p)
            {
                int z=query(u,x,j);
                if(z) x=j;
            }
            int v=0,w=0;
            for(int i=1;i<=n;++i)
            {
                if(x==i||g[i]) continue;
                if(v==0) v=i,w+=f[i];
                else
                {
                    int z=query(v,x,i);
                    if(z==x) w-=f[i];
                    else w+=f[i];
                    if(w==0) v=0;
                    else if(w<0) w=-w,v=i;
                }
            }
            if(v==0) return x;
            for(int i=1;i<=n;++i) h[i]=false;
            for(auto i:p) h[i]=true;
            vector<int> q;
            w=0;
            for(int i=1;i<=n;++i)
            {
                if(x==i||g[i]) continue;
                int z=query(v,x,i);
                if(z!=x)
                {
                    w+=f[i];
                    if(h[i]) q.push_back(i);
                }
                else
                {
                    f[x]+=f[i];
                    g[i]=true;
                }
            }
            if(w<=n/2) return x;
            swap(p,q);
        }
        return 0;
    }
    int main(int _n)
    {
        n=_n;
        while(true)
        {
            int z=solve(rnd(1,n),rnd(1,n));
            if(z) return z;
        }
        return 0;
    }
}
int centroid(int id,int N,int M){
	return Solve::main(N);
}

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:15:5: error: ‘unordered_map’ does not name a type
   15 |     unordered_map<ll,int> Map;
      |     ^~~~~~~~~~~~~
answer.code: In function ‘int Solve::query(int, int, int)’:
answer.code:32:12: error: ‘Map’ was not declared in this scope
   32 |         if(Map.count(s)) return Map[s];
      |            ^~~
answer.code: In function ‘int Solve::solve(int, int)’:
answer.code:39:9: error: ‘Map’ was not declared in this scope
   39 |         Map.clear();
      |         ^~~