#include "richest.h"
#include<bits/stdc++.h>
using namespace std;
const int N = 1e3;
const int M = 1e6;

vector<int> a, b, c;
int w[N + 5][N + 5];

bool vis[M + 5];
int cnt;

int richest(int n, int t, int s){
	if(t == 1){
		a.clear();
		b.clear();
		for(int i = 0; i < n; ++ i){
			for(int j = i + 1; j < n; ++ j){
				a.push_back(i);
				b.push_back(j);
			}
		}
		c = ask(a, b);
		for(int i = 0; i < a.size(); ++ i){
			w[a[i]][b[i]] = w[b[i]][a[i]] = c[i];
			// cout << a[i] << ' ' << b[i] << ": " << c[i] << '\n';
			// cout << w[a[i]][b[i]] << '\n';
		}
		int now = 0;
		for(int i = 1; i < n; ++ i){
			// cout << now << '-' << i << ':' << w[now][i] << '\n';
			if(w[now][i] == i) now = i;
		}
		// cout << now << '\n';
		return now;
	}
	srand(time(0));
	for(int i = 0; i < n; ++ i) vis[i] = 0;
	cnt = 0;
	int ss = s / t;
	while(t --){
		if(cnt == n - 1) break;
		a.clear(); b.clear();
		for(int i = 1; i <= ss; ++ i){
			int x = rand() % n;
			while(vis[x]) x = rand() % n;
			int y = rand() % n;
			while(vis[y] || x == y) y = rand() % n;
			a.push_back(x);
			b.push_back(y);
		}
		c = ask(a, b);
		for(int i = 0; i < c.size(); ++ i){
			if(a[i] == c[i]){
				if(!vis[b[i]]) ++ cnt;
				vis[b[i]] = 1;
			}
			if(b[i] == c[i]){
				if(!vis[a[i]]) ++ cnt;
				vis[a[i]] = 1;
			}
		}
	}
	int now = 0;
	while(vis[now]) ++ now;
	return now;
}