#include "richest.h"
#include<bits/stdc++.h>
//#define int long long
//#define ull unsigned int
//#define lll __int128
//#define double long double
using namespace std;
const long long INF=1e9+5;
//const long long mod=998244353,orm=3;
const long long mod=1000000007;
const int MAXN=2000005;
const double eps=1e-6;
const int MAXN=3000005;
vector<int> A,B,ans,now,v[MAXN];
int n;
int B1[10]={1000000,500000,250000,125000,62497,20832,3472,183,1};
int vis[MAXN];
void clear() {
A.clear(),B.clear(),ans.clear();
}
void calc() {
for(int i=1;i<=n;i++) now.push_back(i);
for(int i=1;i<=8;i++) {
int k=B1[i];
for(int j=0;j<now.size();j++) v[j%k].push_back(now[j]);
for(int j=0;j<k;j++) {
for(int p=0;p<v[j].size();p++) {
for(int q=p+1;q<v[j].size();q++) {
A.push_back(v[j][p]-1),B.push_back(v[j][q]-1);
}
}
}
ans=ask(A,B);int nw=0;
now.clear();
for(int j=0;j<k;j++) {
for(int p=0;p<v[j].size();p++) {
for(int q=p+1;q<v[j].size();q++) {
if(ans[nw++]==v[j][p]-1) vis[v[j][q]]=1;
else vis[v[j][p]]=1;
}
}
for(int p:v[j]) if(!vis[p]) now.push_back(p);v[j].clear();
}
clear();
}
}
void Clear() {
for(int i=0;i<=1000000;i++) {
vis[i]=0;
v[i].clear();
}
clear();now.clear();
}
int O=0,O2=0;
int richest(int N, int T, int S) {
n=N;
if(n<=1000) {
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
A.push_back(i-1),B.push_back(j-1);
}
}
ans=ask(A,B);
int nw=0;
for(int i=1;i<=n;i++) {
for(int j=i+1;j<=n;j++) {
if(ans[nw++]==i-1) vis[j]=1;
else vis[i]=1;
}
}clear();int id=0;
for(int i=1;i<=n;i++) if(!vis[i]) id=i;
Clear();return id-1;
}
calc();
int res=now[0];Clear();
return res-1;
}