#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
int richest(int N, int T, int S)
{
    if (N <= 1000)
    {
        vector<int> A, B, C;
        for (int i = 1; i < N; i++)
        {
            for (int j = 0; j < i; j++)
                A.emplace_back(i), B.emplace_back(j);
        }
        int fa[1010];
        memset(fa, 0, sizeof(fa));
        C = ask(A, B);
        for (int i = 0; i < A.size(); i++)
        {
            int x = A[i], y = B[i], z = C[i];
            if (z == x)
                fa[y] = x;
            else
                fa[x] = y;
        }
        for (int i = 0; i < N; i++)
        {
            if (!fa[i])
                return i;
        }
    }
    else
    {
        int lim = 470;
        vector<int> A;
        for (int i = 0; i < N; i++)
            A.emplace_back(i);
        while (A.size() >= lim)
        {
            int n = A.size();
            vector<int> QA, QB, Ans;
            QA.clear(), QB.clear(), Ans.clear();
            for (int i = 0; i + 1 < A.size(); i += 2)
                QA.emplace_back(A[i]), QB.emplace_back(A[i + 1]);
            Ans = ask(QA, QB);
            if (n & 1)
                Ans.emplace_back(A[n - 1]);
            A = Ans;
        }
        lim = A.size();
        map<int, int> inv;
        vector<int> QA, QB, Ans;
        for (int i = 0; i < lim; i++)
            inv[A[i]] = i;
        for (int i = 1; i < lim; i++)
        {
            for (int j = 0; j < i; j++)
                QA.emplace_back(A[i]), QB.emplace_back(A[j]);
        }
        Ans = ask(QA, QB);
        bool low[1010];
        memset(low, 0, sizeof(low));
        for (int i = 0; i < QA.size(); i++)
        {
            int x = QA[i], y = QB[i], z = Ans[i];
            if (z == x)
                low[inv[y]] = true;
            else
                low[inv[x]] = true;
        }
        for (int i = 0; i < lim; i++)
        {
            if (!low[i])
                return A[i];
        }
        return A[0];
    }
}