#include"lokahia.h"
#include<iostream>
#include<vector>
#include<algorithm>
#define eb emplace_back
#define fi first
#define se second
#define all(x) (x).begin(),(x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int>pi;
typedef pair<ll,ll>pl;
const ll inf=1e18;
int q[205][205];
int query(int x,int y)
{
if(q[x][y]) return q[x][y]-100;
if(q[y][x]) return q[y][x]-100;
q[x][y]=CollectRelics(x,y)+100;
return q[x][y]-100;
}
int FindBase(int N)
{
int cnt=0,tgt=0;
vector<int>tgs,szs;
vector<vector<int> >difs;
int i;
for(i=0;i<N;i++)
{
if(cnt==0)
{
tgt=i;
cnt=1;
tgs.eb(tgt);
szs.eb(1);
difs.eb(vector<int>());
}
else
{
if(query(tgt,i)!=-1)
cnt++,szs[szs.size()-1]++;
else
difs.back().eb(i),cnt--;
}
}
int t=tgs.back();
int n=tgs.size();
cnt=0;
for(i=0;i<n;i++)
{
if(tgs[i]==t)
cnt+=szs[i];
else
{
if(query(tgs[i],t)!=-1)
cnt+=szs[i];
else
for(int m:difs[i])
if(query(t,m)!=-1)
cnt++;
}
}
for(int i=0;i<N;i++){
if(i!=t&&(q[i][t]||q[t][i])){
if(q[i][t]==99||q[t][i]==99) continue;
if(q[i][t]) t=q[i][t]-100;
else t=q[t][i]-100;
break;
}
}
if(cnt>N/2)
return t;
return -1;
}
