#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();
// 	for(int i=0;i<a.size();i++){
// 		cout<<a[i]<<' '<<b[i]<<endl;
// 	}
// 	vector<int>c;
// 	for(int i=0;i<a.size();i++){
// 		int k;cin>>k;
// 		c.push_back(k);
// 	}return c;
// }
inline vector<int> jqh(vector<int> d,int k){
	vector<int>A,B,C;g.clear();
	int len=d.size()/k;
	for(int i=0,j=1;i<d.size();j++){
		int L=len+(j<=d.size()%k);
		for(int a=i;a<i+L;a++){
			for(int b=a+1;b<i+L;b++){
				g[{a,b}]=A.size();
				A.push_back(d[a]),B.push_back(d[b]);
			}
		}i+=L;
	}
	C=ask(A,B);
	vector<int>D;
	for(int i=0,j=1;i<d.size();j++){
		int L=len+(j<=d.size()%k);
		for(int a=i;a<i+L;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<i+L;b++)if(C[g[{a,b}]]!=d[a]){tag=0;break;}
			if(tag){D.push_back(d[a]);break;}
		}i+=L;
	}
	return D;
}
int richest(int n, int T, int S){
	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,500000);
	d=jqh(d,250000);
	d=jqh(d,125000);
	d=jqh(d,62500);
	d=jqh(d,20833);
	d=jqh(d,3472);
	d=jqh(d,183);
	d=jqh(d,1);
	return d.front();
}
// int main(){
// 	cout<<richest(5,10,114514)<<endl;
// 	cout<<cnt<<' '<<sum<<endl;
// }