#include "icc.h"
#include <bits/stdc++.h>
using namespace std;
struct union_find {
int n;
vector<int> par, size;
vector<vector<int> > st;
union_find(int _n) : n(_n), par(n+1), size(n+1, 1), st(n+1) {
for(int i=1; i<=n; i++) {
par[i] = i;
st[i].push_back(i);
}
}
int find(int u) {
if(u == par[u]) return u;
return par[u] = find(par[u]);
}
void uni(int a, int b) {
a = find(a); b = find(b);
if(a == b) return ;
if(size[a] < size[b]) swap(a, b);
for(int &u : st[b]) st[a].push_back(b);
size[a] += size[b];
par[b] = a;
}
bool same_set(int a, int b) {
return find(a) == find(b);
}
} dsu(105);
int __query(vector<int> &x, vector<int> &y) {
int kur[x.size()], picka[y.size()];
for(int i=0; i<x.size(); i++)
kur[i] = x[i];
for(int i=0; i<y.size(); i++)
picka[i] = y[i];
return query(x.size(), y.size(), kur, picka);
}
int _query(vector<int> &a, vector<int> &b) {
vector<int> x, y;
for(int u : a)
for(int v : dsu.st[u])
x.push_back(v);
for(int u : b)
for(int v : dsu.st[u])
y.push_back(v);
int kur[x.size()], picka[y.size()];
for(int i=0; i<x.size(); i++)
kur[i] = x[i];
for(int i=0; i<y.size(); i++)
picka[i] = y[i];
return __query(x, y);
}
void run(int n) {
//ICC = Egoi25 Dark Ride
for(int _=1; _<n; _++) {
vector<int> babi;
for(int i=1; i<=n; i++)
if(dsu.find(i) == i) babi.push_back(i);
int XOR = 0, bit = -1;
for(int b=0; (1<<b)<=n; b++) {
vector<int> v1, v2;
for(int u : babi) {
if(u & (1 << b)) v1.push_back(u);
else v2.push_back(u);
}
if(_query(v1, v2)) {
XOR ^= (1 << b);
bit = b;
}
}
vector<int> v1, v2;
for(int u : babi) {
if(u & (1 << bit)) {
v1.push_back(u);
} else {
v2.push_back(u);
}
}
int l=0, r=v1.size()-1, p=0;
while(l <= r) {
int m = (l + r) / 2;
vector<int> v3;
for(int i=0; i<=m; i++)
v3.push_back(v1[i]);
if(_query(v3, v2)) p = m, r = m - 1;
else l = m + 1;
}
int pu = v1[p];
int pv = pu ^ XOR;
int u = 0;
l=0, r=dsu.st[pu].size()-1;
while(l <= r) {
int m = (l + r) / 2;
vector<int> v3;
for(int i=0; i<=m; i++)
v3.push_back(dsu.st[pu][i]);
if(__query(v3, dsu.st[pv]))
u = dsu.st[pu][m], r = m - 1;
else
l = m + 1;
}
int v = 0;
l=0, r=dsu.st[pv].size()-1;
while(l <= r) {
int m = (l + r) / 2;
vector<int> v3;
for(int i=0; i<=m; i++)
v3.push_back(dsu.st[pv][i]);
if(__query(v3, dsu.st[pu]))
v = dsu.st[pv][m], r = m - 1;
else
l = m + 1;
}
setRoad(u, v);
dsu.uni(u, v);
}
}
