#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define flt double
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()

mt19937 rnd(234);
const ll inf = 1e18;

#include "path.h"

int solve_a(vector<int> a, int lsz, int rsz, int lt, int rt) {
    int sz = a.size();
    if (sz == 1) {
        return a[0];
    }
    int v = a[rnd() % sz];
    int u = lt;
    bool swp = false;
    if (u == -1) {
        u = rt;
        swp = true;
    }
    vector<int> al, ar;
    if (u == -1) {
        u = a[rnd() % sz];
        while (u == v) {
            u = a[rnd() % sz];
        }
        swp = false;
    }
    for (auto x : a) {
        if (x == u || x == v) {
            if (x == u) {
                al.push_back(x);
            }
            continue;
        }
        if (ask(u, v, x) == v) {
            ar.push_back(x);
        } else {
            al.push_back(x);
        }
    }
    if (swp) {
        swap(al, ar);
    }
    if (lsz + (int)al.size() == rsz + (int)ar.size()) {
        return v;
    }
    if (lsz + (int)al.size() > rsz + (int)ar.size()) {
        return solve_a(al, lsz, rsz + (int)ar.size() + 1, lt, v);
    }
    return solve_a(ar, lsz + (int)al.size() + 1, rsz, v, rt);
}

int solve_a(int id, int n, int M) {
    vector<int> a(n);
    for (int i = 0; i < n; i += 1) {
        a[i] = i + 1;
    }
    shuffle(all(a), rnd);
    return solve_a(a, 0, 0, -1, -1);
}

int solve_slow(int id, int n, int M) {
    if (n == 1) {
        return 1;
    }
    pair<int, int> rs = {n, 1};
    vector<vector<int>> d(n + 1, vector<int>(n + 1));
    for (int v = 2; v <= n; v += 1) {
        int cnt = 1;
        for (int u = 2; u <= n; u += 1) {
            if (u == v) {
                continue;
            }
            int t;
            if (u < v) {
                t = d[u][v];
            } else {
                t = ask(1, v, u);
            }
            d[v][u] = d[u][v] = t;
            if (t == v) {
                cnt += 1;
            }
        }
        if (n - cnt <= n / 2) {
            rs = min(rs, make_pair(cnt, v));
        }
    }
    return rs.second;
}

vector<int> sort(vector<int> a, int tl) {
    if ((int)a.size() <= 1) {
        return a;
    }
    int sz = a.size();
    int u = a[rnd() % sz];
    int v = a[rnd() % sz];
    while (v == u) {
        v = a[rnd() % sz];
    }
    if (ask(tl, u, v) == v) {
        swap(u, v);
    }
    vector<int> al, am, ar;
    for (auto x : a) {
        if (x == u || x == v) {
            continue;
        }
        int t = ask(u, x, v);
        if (t == u) {
            al.push_back(x);
        } else if (t == x) {
            am.push_back(x);
        } else {
            ar.push_back(x);
        }
    }
    al = sort(al, tl);
    am = sort(am, u);
    ar = sort(ar, v);
    vector<int> rs;
    for (auto x : al) {
        rs.push_back(x);
    }
    rs.push_back(u);
    for (auto x : am) {
        rs.push_back(x);
    }
    rs.push_back(v);
    for (auto x : ar) {
        rs.push_back(x);
    }
    return rs;
}

int find_pos(vector<int> w, int v) {
    int tl = 0;
    int tr = (int)w.size();
    while (tl + 1 < tr) {
        int tm1 = (tl + tl + tr) / 3;
        int tm2 = (tl + tr + tr) / 3;
        int x = w[tm1];
        int y = w[tm2];
        int t = ask(x, y, v);
        if (t == x) {
            tr = tm1 + 1;
        } else if (t == 0) {
            tl = tm1 + 1;
            tr = tm2 - 1;
        } else {
            tl = tm2;
        }
    }
    return tl;
}

int n;

int solve(int rt, vector<int> a, int itr) {
    if (a.empty()) {
        return rt;
    }
    if (itr >= 50) {
        return rt;
    }
    int v = a[rnd() % (int)a.size()];
    vector<int> al, aw, ar, abd;
    for (auto x : a) {
        if (x == v) {
            continue;
        }
        int t = ask(rt, v, x);
        if (t == 0) {
            abd.push_back(x);
        } else if (t == v) {
            al.push_back(x);
        } else if (t == rt) {
            ar.push_back(x);
        } else {
            aw.push_back(x);
        }
    }
    if ((int)al.size() + 1 > n / 2) {
        return solve(rt, a, itr + 1);
    }
    if ((int)ar.size() + 1 > n / 2) {
        return solve(rt, a, itr + 1);
    }
    aw = sort(aw, v);
    int ln = aw.size();
    vector<vector<int>> b(ln);
    for (auto x : abd) {
        int pos = find_pos(aw, x);
        b[pos].push_back(x);
    }
    b.insert(b.begin(), al);
    aw.insert(aw.begin(), v);
    b.insert(b.end(), ar);
    aw.insert(aw.end(), rt);
    vector<int> f;
    ln += 2;
    for (int i = 0; i < ln; i += 1) {
        for (auto x : b[i]) {
            f.push_back(x);
        }
        f.push_back(aw[i]);
        if ((int)f.size() > n / 2) {
            break;
        }
    }
    int nrt = f.back();
    f.pop_back();
    int rs = solve(nrt, f, itr + 1);
    return rs;
}

int solve(int id, int N, int M) {
    n = N;
    int rt = 1;
    vector<int> a;
    for (int i = 1; i <= n; i += 1) {
        if (i != rt) {
            a.push_back(i);
        }
    }
    shuffle(all(a), rnd);
    int rs = solve(rt, a, 0);
    return rs;
}

int centroid(int id, int N, int M) {
    if (id == 3 || id == 5) {
        return solve_a(id, N, M);
    }
    return solve(id, N, M);
}