#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
int p[205];
int sz[205];
int findSet(int u){
if(u == p[u]) return u;
else return findSet(p[u]);
}
int SZ(int u){ return sz[findSet(u)]; }
void unionSet(int u, int P){
u = findSet(u), P = findSet(P);
p[u] = P;
sz[P] += sz[u];
}
int FindBase(int N){
srand(time(NULL));
vector<int> v;
if(N == 1){
return 0;
}
for(int i = 0;i < N;i++) v.push_back(i);
for(int i = 0;i < N;i++){
p[i] = i;
sz[i] = 1;
}
int cnt = 0;
map<int,int> occur;
vector<int> P;
for(int i = N/4;i < N;i++){
for(int j = 0;j < i*i;j++) P.push_back(i);
}
while(cnt < 200){
int a = P[rand() % P.size()], b = P[rand() % P.size()];
if(a == b) continue;
cnt++;
int x = CollectRelics(a,b);
occur[x]++;
}
int best = 0;
for(int i = 0;i < N;i++){
if(occur[best] < occur[i]){
best = i;
}
}
int total = 0;
for(int i = 0;i < N;i += 2){
if(i == best){
total++;
continue;
}
if(CollectRelics(i,best) != -1) total++;
}
//cout << best;
if(total > (N/2)) return best;
//assert(false);
//cout << best;
return -1;
}
