#include <bits/stdc++.h>
#include "lokahia.h"
#define maxn 205
using namespace std;
int cnt, ch[maxn][maxn];
const int mxs = 600;
int q(int a, int b) {
if (cnt >= mxs) return -1;
if (ch[a][b] != -1) return ch[a][b] - 1;
cnt++;
ch[a][b] = ch[b][a] = CollectRelics(a, b) + 1;
return ch[a][b] - 1;
}
int fl[maxn];
int d[maxn];
int FindBase(int N) {
cnt = 0;
for (int i = 0; i < N; i++)
d[i] = i;
memset(ch, -1, sizeof(ch));
while (1) {
memset(fl, 0, sizeof(fl));
random_shuffle(d, d + N);
int nr = d[0], sz = 0;
for (int i = 1; i < N; i++)
{
int nans = q(nr, d[i]);
if (nans == -1) continue;
else
sz++, nr = nans;
}
// cout << nr << ' ' << sz << endl;
if (sz >= N / 2) return nr;
if (cnt >= mxs) break;
}
return -1;
}
