#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
vector<int> par;
int getpar(int x){
if(par[x] != x){
par[x] = getpar(par[x]);
}
return par[x];
}
int FindBase(int N){
//int par[N];
int disjointtotal = 0;
queue<int> ndjol; //not disjoint or lone
int curgrpsize = 1;
for(int i = 0; i < N; ++i){
par.push_back(i);
ndjol.push(i);
}
ndjol.push(N); //end of pairing
int llone = -1; //largest lone
while(ndjol.size() > 1){
int frst = ndjol.front();
frst = getpar(frst);
ndjol.pop();
if(frst == N){
ndjol.push(N);
curgrpsize <<= 1;
continue;
}
int scnd = ndjol.front();
ndjol.pop();
scnd = getpar(scnd);
if(scnd == N){
ndjol.push(N);
curgrpsize <<= 1;
llone = frst;
continue;
}
int res = frst;
if(frst != scnd) res = CollectRelics(frst, scnd);
if(res == -1){
disjointtotal += curgrpsize;
if(disjointtotal * 2 >= N){
return -1;
}
}else{
res = getpar(res);
par[frst] = res;
par[scnd] = res;
ndjol.push(res);
}
}
if(llone == -1){
return -1;
}
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;
}
