#include "lokahia.h"
#include<bits/stdc++.h>
using namespace std;
mt19937_64 rng(94949);
int R(int a, int b)
{
return uniform_int_distribution<int>(a, b)(rng);
}
int FindBase(int N){
if(N==1) return 0;
vector<int> cnt(N);
for(int i=0; i<400-2*N+3; ++i)
{
int v1, v2;
do
{
v1 = R(0, N-1);
v2 = R(0, N-1);
} while (v1==v2);
int x = CollectRelics(v1, v2);
if(x != -1) cnt[x] ++;
}
int maxi = max_element(cnt.begin(), cnt.end()) - cnt.begin();
cnt[maxi] = -1;
int maxi2 = max_element(cnt.begin(), cnt.end()) - cnt.begin();
int cc = 1;
int mim2=0;
for(int i=0; i<N; ++i)
if(i != maxi && -1 != CollectRelics(maxi, i))
{
++cc;
if(i==maxi2) mim2=1;
}
if(cc > N/2) return maxi;
cc = 1 + mim2;
for(int i=0; i<N; ++i)
if(i != maxi2 && i!=maxi && -1 != CollectRelics(maxi2, i))
++cc;
if(cc > N/2) return maxi2;
else return -1;
}
