/* cerberus97 - Hanit Banga */
#include <iostream>
#include <iomanip>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include "lokahia.h"
using namespace std;
#define pb push_back
#define fast_cin() ios_base::sync_with_stdio(false); cin.tie(NULL)
typedef long long ll;
typedef long double ld;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;
const int N = 2e2 + 10;
int par[N], sz[N];
int get_root(int u);
void merge(int u, int v);
int ask(int u, int v);
int FindBase(int n) {
for (int i = 0; i < n; ++i) {
par[i] = i;
sz[i] = 1;
}
int u = -1, ctr = 0;
for (int i = 0; i < n; ++i) {
if (ctr == 0) {
u = i;
ctr = 1;
} else {
int l = ask(u, i);
if (l == -1) {
--ctr;
} else {
++ctr;
merge(u, l);
merge(i, l);
}
}
}
for (int i = 0; i < n; ++i) {
if (par[i] == i) {
int v = ask(u, i);
if (v != -1) {
merge(u, v);
merge(i, v);
}
}
}
u = get_root(u);
if (sz[u] > n / 2) {
return u;
} else {
return -1;
}
}
int get_root(int u) {
if (par[u] != u) {
par[u] = get_root(par[u]);
}
return par[u];
}
void merge(int u, int v) {
u = get_root(u);
v = get_root(v);
if (u != v) {
par[u] = v;
sz[v] += sz[u];
}
}
int ask(int u, int v) {
u = get_root(u);
v = get_root(v);
if (u == v) {
return u;
} else {
return CollectRelics(u, v);
}
}
