#include "lokahia.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> PII;
int FindBase(int N){
int n = N;
if (n == 1) return 0;
// if (n <= 17) {
// vector<int> g(n, 0);
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < n; j++) if (i != j) {
// int k = CollectRelics(i, j);
// if (k != -1) {
// g[k] |= (1 << i) | (1 << j);
// }
// }
// }
// }
srand(time(NULL));
int qaq = 298 - n;
vector<int> f(n, 0);
for (int i = 1; i <= qaq; i++) {
int x = rand() % n, y = rand() % n;
while (x == y) {
x = rand() % n, y = rand() % n;
}
int k = CollectRelics(x, y);
if (k != -1) f[k]++;
}
int u = 0;
for (int i = 1; i < n; i++)
if (f[i] > f[u]) u = i;
int cnt = 0;
for (int i = 0; i < n; i++) if (i != u) {
int k = CollectRelics(u, i);
if (k != -1) cnt++;
}
if (cnt >= n / 2) return u;
return -1;
}
