#include "path.h"

#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> ostream &operator<<(ostream &os, const vector<T> &as) { const int sz = as.size(); os << "["; for (int i = 0; i < sz; ++i) { if (i >= 256) { os << ", ..."; break; } if (i > 0) { os << ", "; } os << as[i]; } return os << "]"; }
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }
#define COLOR(s) ("\x1b[" s "m")

#include <random>



int centroid(int ID, int N, int M) {
  mt19937_64 rng;
  if (ID == 1 || ID == 3 || ID == 5) {
    int l = 0, r = N;
    vector<int> us(N);
    for (int u = 1; u <= N; ++u) us[u - 1] = u;
    for (; ; ) {
      assert(l <= N / 2); assert(N / 2 < r);
      auto sayuu = [&](int &s, int &t) -> void {
        if (0 < l) {
          const int res = ask(us[0], s, t);
          if (res == s) {
            //
          } else if (res == t) {
            swap(s, t);
          } else {
            assert(false);
          }
        } else if (r < N) {
          const int res = ask(s, t, us[N - 1]);
          if (res == s) {
            swap(s, t);
          } else if (res == t) {
            //
          } else {
            assert(false);
          }
        } else {
          //
        }
      };
      if (r - l == 1) {
        return us[N/2];
      } else if (r - l == 2) {
        assert(0 < l || r < N);
        sayuu(us[l], us[l + 1]);
        return us[N/2];
      } else {
        int s, t;
        for (; ; ) {
          s = us[l + rng() % (r - l)];
          t = us[l + rng() % (r - l)];
          if (s != t) break;
        }
        sayuu(s, t);
        vector<int> vss[3];
        for (int j = l; j < r; ++j) {
          const int u = us[j];
          if (s != u && t != u) {
            const int res = ask(s, t, u);
            if (res == s) {
              vss[0].push_back(u);
            } else if (res == t) {
              vss[2].push_back(u);
            } else if (res == u) {
              vss[1].push_back(u);
            } else {
              assert(false);
            }
          }
        }
        int pos = l;
        for (const int v : vss[0]) us[pos++] = v;
        const int posS = pos; us[pos++] = s;
        for (const int v : vss[1]) us[pos++] = v;
        const int posT = pos; us[pos++] = t;
        for (const int v : vss[2]) us[pos++] = v;
        assert(pos == r);
        const int cuts[6] = {l, posS, posS + 1, posT, posT + 1, r};
        for (int k = 0; k < 6; ++k) {
          assert(k < 5);
          if (cuts[k] <= N/2 && N/2 < cuts[k + 1]) {
            l = cuts[k];
            r = cuts[k + 1];
            break;
          }
        }
      }
    }
  } else {
    vector<int> sz(N + 1, 0);
    for (int u = 1; u <= N; ++u) sz[u] = 1;
    vector<int> us(N);
    for (int u = 1; u <= N; ++u) us[u - 1] = u;
    for (; ; ) {
// cerr<<"sz = "<<sz<<", us = "<<us<<endl;
      assert(us.size() >= 2);
      int s, t;
      for (; ; ) {
        s = us[rng() % us.size()];
        t = us[rng() % us.size()];
        if (s != t) break;
      }
      vector<int> uss[4];
      for (const int u : us) if (s != u && t != u) {
        const int res = ask(s, t, u);
        uss[(res == s) ? 0 : (res == u) ? 1 : (res == t) ? 2 : 3].push_back(u);
      }
      int sums[4] = {};
      for (int k = 0; k < 4; ++k) for (const int u : uss[k]) sums[k] += sz[u];
// cerr<<"  s = "<<s<<", t = "<<t<<endl;
// cerr<<"  uss = ";pv(uss,uss+4);
// cerr<<"  sums = ";pv(sums,sums+4);
      if (sums[0] > N/2) {
        sz[s] += (sz[t] + sums[1] + sums[2] + sums[3]);
        us = uss[0];
        us.push_back(s);
      } else if (sums[2] > N/2) {
        sz[t] += (sz[s] + sums[0] + sums[1] + sums[3]);
        us = uss[2];
        us.push_back(t);
      } else {
        // TODO: ternary?
        sort(uss[1].begin(), uss[1].end(), [&](int u, int v) -> bool {
          return (ask(s, u, v) == u);
        });
        // !
        uss[1].insert(uss[1].begin(), s);
        uss[1].push_back(t);
        const int len1 = uss[1].size();
        vector<vector<int>> vss(len1);
        for (const int v : uss[3]) {
          int lo = 1, hi = len1 - 1;
          for (; lo + 1 < hi; ) {
            const int midL = lo + (hi - lo + 2) / 3;
            const int midR = hi - (hi - lo + 2) / 3;
            assert(lo < midL); assert(midL <= midR); assert(midR < hi);
            const int res = ask(uss[1][midL - 1], uss[1][midR], v);
            if (res == uss[1][midL - 1]) {
              hi = midL;
            } else if (res == 0) {
              lo = midL;
              hi = midR;
            } else if (res == uss[1][midR]) {
              lo = midR;
            } else {
              assert(false);
            }
          }
          vss[lo].push_back(v);
        }
// cerr<<"  uss[1] = "<<uss[1]<<", vss = "<<vss<<endl;
        vector<int> fs(len1, 0), gs(len1, 0);
        vector<int> fsSum(len1 + 1, 0), gsSum(len1 + 1, 0);
        for (int j = 0; j < len1; ++j) {
          fs[j] = sz[uss[1][j]];
          for (const int v : vss[j]) gs[j] += sz[v];
          fsSum[j + 1] = fsSum[j] + fs[j];
          gsSum[j + 1] = gsSum[j] + gs[j];
        }
        for (int j = 0; j < len1; ++j) {
          int sumL = 0, sumR = 0;
          sumL += sums[0];
          sumL += fsSum[j];
          sumL += gsSum[j];
          sumR += sums[2];
          sumR += (fsSum[len1] - fsSum[j + 1]);
          sumR += (gsSum[len1] - gsSum[j + 1]);
          if (sumL <= N/2 && sumR <= N/2) {
            const int u = uss[1][j];
            if (gs[j] <= N/2) {
              return u;
            } else {
              sz[u] += (sumL + sumR);
              us = vss[j];
              us.push_back(u);
              goto found;
            }
          }
        }
        assert(false);
       found:{}
      }
    }
  }
}