#include "richest.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vec;
const int MAXN = 1e6;
int n,deg[MAXN]; vec a,b,c;
int cur;

void reset(){a.clear(); b.clear();}
void link(int x,int y){a.push_back(x); b.push_back(y);}

int tag[MAXN],arr[MAXN],len[MAXN],tot;

void solve(int cnt){
    tot = 0; for(int i=0;i<n;i++)if(!tag[i])arr[tot++] = i;
    for(int i=0;i<cnt;i++)len[i] = tot/cnt + (i<tot%cnt);
    reset();
    for(int i=0,sum=0;i<cnt;sum+=len[i],i++){
        for(int j=0;j<len[i];j++)for(int k=j+1;k<len[i];k++)link(arr[sum+j],arr[sum+k]);
    }
    c = ask(a,b); cur = 0;
    for(int i=0,sum=0;i<cnt;sum+=len[i],i++){
        for(int j=0;j<len[i];j++)deg[arr[sum+j]] = 0;
        for(int j=0;j<len[i];j++)for(int k=j+1;k<len[i];k++){
            int v = c[cur++];
            deg[v]++;
        }
        for(int j=0;j<len[i];j++)if(deg[arr[sum+j]] != len[i]-1)tag[arr[sum+j]] = 1;
    }
}

int richest(int N,int _,int __){
    n = N;
    if(n==1000){
        reset();
        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++)link(i,j);
        c = ask(a,b); cur = 0;
        fill(deg,deg+n,0);
        for(int i=0;i<n;i++)for(int j=i+1;j<n;j++){
            int v = c[cur++];
            deg[v]++;
        }
        for(int i=0;i<n;i++)if(deg[i] == n-1)return i;
        return -1;
    }
    fill(tag,tag+n,0);
    solve(n/2); solve(n/4); solve(n/8); solve(n/16); solve(20832); solve(3472); solve(183); solve(1);
    for(int i=0;i<n;i++)if(!tag[i])return i;
    return -1;
}