#include"lokahia.h"
#include<cstring>
#include<vector>
#include<ctime>
#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 pa[205],sz[205];
int par(int x)
{
if(pa[x]==-1)
return x;
return pa[x]=par(pa[x]);
}
int C[205];
vector<int>v;
bool chk[205][205];
int cnt;
int FindBase(int N)
{
if(N==1)
return 0;
int i;
for(i=0;i<N;i++)
v.eb(i);
memset(pa,-1,sizeof pa);
fill(sz,sz+205,1);
for(i=0;i<600&&cnt<500000&&v.size()>1;i++,cnt++)
{
int n=rand()%v.size();
int j=n;
while(j==n)
j=rand()%v.size();
n=v[n];
j=v[j];
if(chk[n][j])
{
i--;
continue;
}
chk[n][j]=true;
int t=CollectRelics(n,j);
if(t!=-1)
{
t=par(t);
if(n!=t)
{
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
if(*it==n)
break;
it++;
}
v.erase(it);
pa[n]=t;
sz[t]+=sz[n];
}
n=j;
if(n!=t)
{
vector<int>::iterator it=v.begin();
while(it!=v.end())
{
if(*it==n)
break;
it++;
}
v.erase(it);
pa[n]=t;
sz[t]+=sz[n];
}
}
}
for(i=0;i<N;i++)
if(pa[i]==-1&&sz[i]>=N/2)
break;
if(i>=N)
return-1;
return sz[i];
}
