#include "lokahia.h"
#include <vector>
using namespace std;
vector<int> my[202], adv[202];
int gcn, res[202][202], cnts[202];
int comp(int x, int y){
if(res[x][y]==-2) return res[x][y]=res[y][x]=CollectRelics(x,y);
return res[x][y];
}
int FindBase(int N){
for(int i=0; i<N; i++){
for(int j=0; j<N; j++) res[i][j]=-2;
}
my[gcn].push_back(0);
for(int i=1; i<N; i++){
int d = comp(my[gcn][0], i);
if(d<0) adv[gcn].push_back(i);
else my[gcn].push_back(i);
if(my[gcn].size() == adv[gcn].size()){
i++, gcn++;
if(i==N) return -1;
my[gcn].push_back(i);
}
}
int myt=my[gcn].size();
for(int i=0; i<gcn; i++){
if(comp(my[i][0], my[gcn][0]) < 0){
for(auto &x: adv[i]){
int d = comp(x, my[gcn][0]);
if(d>=0) myt++, cnts[d]++;
}
}
else{
for(auto &x: my[i]){
int d = comp(x, my[gcn][0]);
if(d>=0) myt++, cnts[d]++;
}
}
}
for(auto &x: my[gcn]){
if(x==my[gcn][0]) continue;
cnts[comp(x, my[gcn][0])]++;
}
if(myt <= N/2) return -1;
int mx=-1, mxi=0;
for(int i=0; i<N; i++){
if(cnts[i]>mx) mx=cnts[i], mxi=i;
}
return mxi;
}
