#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
vector<bool> matched;
int getpar(int x){
//printf("getpar %d\n", x);
if(par[x] != x){
par[x] = getpar(par[x]);
}
return par[x];
}
int FindBase(int N){
//int par[N];
int disjointtotal = 0;
for(int i = 0; i < N; ++i){
par.push_back(i);
matched.push_back(false);
}
int frst;
while(true){
frst = -1;
bool fin = true;
for(int i = 0; i < N; ++i){
if(matched[i]) continue;
if(frst == -1){
frst = i;
continue;
}
if(getpar(frst) != getpar(i)){
int res = CollectRelics(getpar(frst), getpar(i));
if(res == -1){
++disjointtotal;
if(disjointtotal * 2 >= N) return -1;
matched[i] = matched[frst] = true;
}else{
res = getpar(res);
par[getpar(frst)] = res;
par[getpar(i)] = res;
}
fin = false;
break;
}
}
if(fin) break;
}
int llone = frst; //yes, this is copypasted.
for(int i = 0; i < N; ++i){
if(i == llone || par[i] != i) continue;
int res = CollectRelics(i, llone);
if(res == -1) continue;
res = getpar(res);
par[llone] = res;
par[i] = res;
llone = res;
}
int llonesize = 0;
for(int i = 0; i < N; ++i){
if(getpar(i) == llone) llonesize++;
}
if(llonesize * 2 > N) return llone;
//CollectRelics()
return -1;
}
