#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;
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;
}