#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
// void setRoad(int a, int b);
// int query(int sz_a, int sz_b, int a[], int b[]);
const int MAXN = 110;
const int LOG = 7;
int a[LOG][MAXN], b[LOG][MAXN];
int sz_a[LOG], sz_b[LOG];
int pai[MAXN], comp[MAXN];
int cur_A[MAXN], cur_B[MAXN];
int bit;
int get(int v){
if(v == pai[v]) return v;
return pai[v] = get(pai[v]);
}
void dsu_union(int a, int b){
a = get(a); b = get(b);
pai[a] = b;
}
bool check_A(int m){
int cur_sz = m + 1;
for(int i=0; i<cur_sz; i++) cur_A[i] = a[bit][i];
for(int i=0; i<sz_b[bit]; i++) cur_B[i] = b[bit][i];
return query(cur_sz, sz_b[bit], cur_A, cur_B);
}
int bs_A(){
int l = 0, r = sz_a[bit];
while(l < r){
int m = l + (r - l) / 2;
if(check_A(m)) r = m;
else l = m + 1;
}
return r;
}
bool check_B(int m){
int cur_sz = m + 1;
for(int i=0; i<sz_a[bit]; i++) cur_A[i] = a[bit][i];
for(int i=0; i<cur_sz; i++) cur_B[i] = b[bit][i];
return query(sz_a[bit], cur_sz, cur_A, cur_B);
}
int bs_B(){
int l = 0, r = sz_b[bit] - 1;
while(l < r){
int m = l + (r - l) / 2;
if(check_B(m)) r = m;
else l = m + 1;
}
return r;
}
void solve(int n){
int cnt = 0;
for(int i=1; i<=n; i++) if(i == get(i)) comp[i] = cnt++;
int log = __lg(cnt) + 1;
for(int i=0; i<log; i++){
sz_a[i] = sz_b[i] = 0;
for(int j=1; j<=n; j++){
if(comp[get(j)] & (1 << i)){
a[i][sz_a[i]++] = j;
} else b[i][sz_b[i]++] = j;
}
}
bit = -1;
for(int i=0; i<log; i++){
if(query(sz_a[i], sz_b[i], a[i], b[i])){
bit = i;
break;
}
}
int pos_a = bs_A(), pos_b = bs_B();
setRoad(a[bit][pos_a], b[bit][pos_b]);
dsu_union(a[bit][pos_a], b[bit][pos_b]);
}
void run(int n){
for(int i=1; i<=n; i++) pai[i] = i;
for(int i=0; i<(n - 1); i++) solve(n);
}
