#include "richest.h"

using std::vector;

int richest(int N, int T, int S) {
  if (T == 1) {
    vector<int> as, bs;
    for (int u = 0; u < N; ++u) for (int v = u + 1; v < N; ++v) {
      as.push_back(u);
      bs.push_back(v);
    }
    const auto res = ask(as, bs);
    vector<int> freq(N, 0);
    for (const int u : res) ++freq[u];
    for (int u = 0; u < N; ++u) if (freq[u] == N - 1) return u;
    return -1;
  } else {
    constexpr int Ks[8] = {
      500000,
      250000,
      125000,
       62500,
       20832,
        3472,
         183,
           1,
    };
    vector<int> us(N);
    for (int u = 0; u < N; ++u) us[u] = u;
    for (int t = 0; t < 8; ++t) {
      const int K = Ks[t];
      vector<vector<int>> vss(K);
      for (int i = 0; i < (int)us.size(); ++i) vss[i % K].push_back(us[i]);
      vector<int> as, bs;
      for (int k = 0; k < K; ++k) {
        const auto &vs = vss[k];
        for (int x = 0; x < (int)vs.size(); ++x) for (int y = x + 1; y < (int)vs.size(); ++y) {
          as.push_back(vs[x]);
          bs.push_back(vs[y]);
        }
      }
      const auto res = ask(as, bs);
      vector<int> freq(N, 0);
      for (const int u : res) ++freq[u];
      us.resize(K);
      for (int k = 0; k < K; ++k) {
        const auto &vs = vss[k];
        us[k] = -1;
        for (const int u : vs) if (freq[u] == (int)vs.size() - 1) us[k] = u;
      }
    }
    return us[0];
  }
}