#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;
// }
inline vector<int> jqh(vector<int> d,int k){
	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;}
		}
	}
	return D;
}
int richest(int n, int T, int S){
	// int len[9]={2,2,2,2,4,6,19,34,34};
	int len[8]={2,2,2,2,3,6,19,183};
	// int len[7]={2,2,3,3,7,20,199};
	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);
	d=jqh(d,2);
	d=jqh(d,2);
	d=jqh(d,2);
	d=jqh(d,2);
	d=jqh(d,3);
	d=jqh(d,6);
	d=jqh(d,19);
	d=jqh(d,183);
	return d.front();
}
// int main(){
// 	cout<<richest(1000000,10,2000000)<<endl;
// 	cout<<cnt<<' '<<sum<<endl;
// }