#include "lokahia.h"
#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
using namespace std;
using group = pair<vector<int>, vector<int>>;
int lca(int x, int y){
return x == y ? x : CollectRelics(x, y);
}
int FindBase(int N){
vector<group> grp;
group g;
for(int i=0; i<N; i++){
if(sz(g.first) == 0){
g.first.push_back(i);
continue;
}
int query = lca(g.first[0], i);
if(query == -1){
g.second.push_back(i);
}
else{
g.first.push_back(i);
g.first[0] = query;
}
if(sz(g.first) == sz(g.second)){
grp.push_back(g);
group h; g = h;
}
}
if(sz(g.first)) grp.push_back(g);
int who = grp.back().first[0];
int cnt = 0;
for(auto &i : grp){
int comp = lca(i.first[0], who);
if(comp != -1){
who = comp;
cnt += sz(i.first);
}
else{
for(auto &j : i.second){
int L = lca(who, j);
if(L != -1) who = L, cnt++;
}
}
}
if(cnt >= N / 2 + 1) return who;
return -1;
}
