#include "lokahia.h"
#include <vector>
#include <queue>
using namespace std;
int h[300];
int sz[300];
typedef pair<int,int> pii;
vector<int> q,nq;
vector<pii> Q;
vector<pii> lft;
bool merge(int x, int y) {
int t;
if(h[x]==h[y]) t=h[x];
else t=CollectRelics(h[x],h[y]);
if(t<0) return false;
h[x]=t;
sz[x]+=sz[y];
return true;
}
int FindBase(int N){ int n=N;
for(int i=0; i<n; i++) q.push_back(i), h[i]=i, sz[i]=1;
for(int i=0; !q.empty(); i++) {
nq.clear();
for(int i=0; i<10; i+=2) {
if(i==(int)q.size()-1) {
lft.push_back({q[i], i});
}
if(merge(q[i], q[i+1])) {
nq.push_back(q[i]);
} else {
Q.push_back({q[i], q[i+1]});
}
}
q=nq;
}
if(lft.empty()) return -1;
int X=lft.back().first;
for(int i=0; i<(int)lft.size()-1; i++) merge(X, lft[i].first);
for(int i=0; i<(int)Q.size(); i++) merge(X, Q[i].first), merge(X, Q[i].second);
if(sz[X]>(n/2)) return h[X];
else return -1;
}
