// Source: https://usaco.guide/general/io
//pls AC owo
#include <bits/stdc++.h>
#include "richest.h"
using namespace std;
int solveSmall(int n){//task 1 is just a n^2 brute force
//simmilar to first explore task
//surely
	vector<int> x,y;
	for(int i=0;i<n;i++){
		for(int j=i+1;j<n;j++){
			x.push_back(i),y.push_back(j);
		}
	}
	vector<int> z=ask(x,y),cnt(n);//ask-2005 refrence 0-0
	for(auto&i:z){
		cnt[i]++;
		if(cnt[i]==n-1)return i;
	}
	return 0;
}
int solveLarge(int n){//bucket sort idea
//solution is to split the entire thing up into sections
//find largest in each section then split it down
	vector<int>idx(n);
	for(int i=0;i<n;i++)
		idx[i]=i;
	
	vector<int>szs={
		(int)5e5,
		(int)25e4,
		(int)125e3,
		(int)625e2,
		(int)20832,
		(int)3472,
		(int)183,
		(int)1};
	for(int U=0;U<8;U++){
		vector<vector<int>>asks(szs[U]);
		for(int i=0;i<idx.size();i++){//buckets yay
			asks[i%szs[U]].push_back(idx[i]);
		}
		vector<int> x,y;
		for(int i=0;i<szs[U];i++)
			for(int j=0;j<asks[i].size();j++)
				for(int k=j+1;k<asks[i].size();k++)
					x.push_back(asks[i][j]),y.push_back(asks[i][k]);
		vector<int>z=ask(x,y),cnt(n);
		for(auto&i:z)
			cnt[i]++;
		idx.resize(szs[U]);
		for(int i=0;i<szs[U];i++){
			idx[i]=-1;
			for(auto&j:asks[i]){
				if(cnt[j]==asks[i].size()-1){
					idx[i]=j;
				}
			}
		}
	}
	return idx[0];
}
int richest(int n, int t,int s){
	if(t==1)return solveSmall(n);
	return solveLarge(n);
}