#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
int FindBase(int n){
if(n == 1) return 0;
mt19937 gen(time(NULL));
uniform_int_distribution<int> uid(0, n - 1);
vector<int> cnt(n);
int rep = 401;
for(int i = 0; i < rep; ++i){
int x = uid(gen), y = uid(gen);
while(x == y){
y = uid(gen);
}
int rv = CollectRelics(x, y);
if(rv != -1){
++cnt[rv];
}
}
int mx = 0, pos = -1;
for(int i = 0; i < n; ++i){
if(cnt[i] > mx){
mx = cnt[i];
pos = i;
}
}
if(pos == -1) return -1;
int gocnt = 1;
for(int i = 0; i < n; ++i){
if(i == pos) continue;
gocnt += (CollectRelics(pos, i) != -1);
}
if(gocnt > n / 2) return pos;
return -1;
}
