#include "lokahia.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define fi first
#define se second
#define mp make_pair
#define pb push_back
typedef long long ll;
typedef pair<int,int> ii;
typedef vector<int> vi;
typedef unsigned long long ull;
typedef long double ld;
typedef tree<ii, null_type, less<ii>, rb_tree_tag, tree_order_statistics_node_update> pbds;
int used[222];
int rtnumber[222];
map<ii,int> ma;
int ask(int u, int v)
{
if(ma.find({u,v})!=ma.end()) return ma[{u,v}];
return (ma[{u,v}]=ma[{v,u}]=CollectRelics(u,v));
}
int FindBase(int N)
{
int n=N;
if(n==1) return 0;
if(n==2)
{
return ask(0,1);
}
memset(used,0,sizeof(used));
set<int> S;
int rt=-1;
for(int i=0;i<n;i++)
{
if(used[i]) continue;
if(rt==-1)
{
S.insert(i); used[i]=1; rt=i; continue;
}
int newrt = ask(rt,i);
if(newrt==-1)
{
auto it = (prev(S.end()));
if(S.size()==1)
{
used[rt]=used[i]=1;
S.clear(); rt=-1; continue;
}
while((*it)==rt)
{
it--;
}
S.erase(it);
used[i]=1;
continue;
}
S.insert(i);
S.insert(newrt);
rt=newrt;
}
if(S.empty())
{
return -1;
}
int u = (*S.begin());
int mx=-1;
int cnt=1;
for(int i=0;i<n;i++)
{
if(i!=u)
{
rtnumber[i]=ask(i,u);
mx=max(mx,rtnumber[i]);
}
}
if(mx<0) return -1;
for(int i=0;i<n;i++)
{
if(i==mx) continue;
cnt+=(ask(i,mx)!=-1);
}
if(cnt*2>n) return mx;
else return -1;
}
