#include<bits/stdc++.h>
#include "richest.h"
using namespace std;
int id[1005][1005],ins[1000005];
map<pair<int,int>,int>g;
int cnt,sum;
// vector<int> ask(vector<int>a,vector<int>b){
// 	cnt++,sum+=a.size();
// 	vector<int>c;
// 	for(int i=0;i<a.size();i++){
// 		c.push_back(b[i]);
// 	}return c;
// }
int richest(int n, int T, int S){
	int len[9]={2,2,2,2,4,6,19,34,34};
	if(n==1000){
		vector<int>A,B;
		for(int i=0;i<n;i++){
			for(int j=i+1;j<n;j++){
				id[i][j]=A.size(),A.push_back(i),B.push_back(j);
			}
		}
		auto C=ask(A,B);
		for(int i=0;i<n;i++){
			bool tag=1;
			for(int j=0;j<i;j++)if(C[id[j][i]]!=i)tag=0;
			for(int j=i+1;j<n;j++)if(C[id[i][j]]!=i)tag=0;
			if(tag)return i;
		}
	}
	vector<int>d;
	for(int i=0;i<n;i++)d.push_back(i);
	// int k=2;
	// while(ceil(log(n)/log(k+1))>T)k++;
	// int k=5,len=5;
	for(int t=0;t<9;t++){
		int k=len[t];
		vector<int>A,B,C;g.clear();
		for(int i=0;i<d.size();i+=k){
			int r=min(i+k,(int)d.size());
			for(int a=i;a<r;a++){
				for(int b=a+1;b<r;b++){
					g[{a,b}]=A.size();
					A.push_back(d[a]),B.push_back(d[b]);
				}
			}
		}
		C=ask(A,B);
		vector<int>D;
		for(int i=0;i<d.size();i+=k){
			int r=min(i+k,(int)d.size());
			for(int a=i;a<r;a++){
				bool tag=1;
				for(int b=i;b<a;b++)if(C[g[{b,a}]]!=d[a]){tag=0;break;}
				for(int b=a+1;b<r;b++)if(C[g[{a,b}]]!=d[a]){tag=0;break;}
				if(tag){D.push_back(d[a]);break;}
			}
		}
		d=D;
	}
	return d.front();
}
// int main(){
// 	cout<<richest(1000000,10,2000000)<<endl;
// 	cout<<cnt<<' '<<sum<<endl;
// }