#include "soul.h"
#include <bits/stdc++.h>
#define rep(i, j, k) for (int i = j; i <= k; i++)
#define pb push_back
using namespace std;
mt19937 rng(time(0));
const int N = 1e5 + 5;
int n, tot, u, v, szu, szv, t[N];
vector<int> vec, nv, chain;
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, a.x, b.x) == a.x;
    }
} a[N];
int js(int x) {
    if (t[x] == x) return x;
    int res = 0;
    for (auto dq : chain)
        if (!res) res = dq;
        else res = ask(res, x, dq);
    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 sol() {
    chain.clear(), nv.clear();
    for (int x : vec) {
        int c = ask(u, v, x);
        t[x] = c;
        if (c == u) szu++;
        else if (c == v) szv++;
        else if (c == x) chain.pb(x), nv.pb(x);
        else nv.pb(x);
    }
    if (szu * 2 > n || szv * 2 > n) return 0;
    int p = js(nv[rng() % 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 sol();
}
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 = rng() % n + 1, v = rng() % n + 1;
        while (u == v)
            u = rng() % n + 1, v = rng() % n + 1;
        vec.clear(), nv.clear(), chain.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:1:10: fatal error: soul.h: No such file or directory
    1 | #include "soul.h"
      |          ^~~~~~~~
compilation terminated.