#include "bits/stdc++.h"
#include "icc.h"
#define pb push_back
#define si(a_) (ll)(a_.size())
using namespace std;
using ll = int;
const ll maxn = 105;
const ll lg = 7;
ll n;
ll a[maxn];
ll b[maxn];
ll c[maxn];
ll asz = 0,bsz = 0,csz = 0;
ll dsu[maxn];
vector<ll> v[maxn];
set<ll> s;
ll root(ll x){
while(x!=dsu[x]){
x = dsu[x];
}
return x;
}
void upd(ll x,ll y){
x = root(x), y = root(y);
dsu[y] = x;
for(ll u : v[y]) v[x].pb(u);
}
void run(ll N){
n = N;
for(ll i = 1;i<=n;i++){
v[i].pb(i);
dsu[i] = i;
}
// freopen("out.txt","w",stdout);
for(ll ff = 0;ff<n-1;ff++){
vector<ll> rut;
s.clear();
for(ll i = 1;i<=n;i++) s.insert(root(i));
for(ll x : s) rut.pb(x);
// cout<<"RUT: "<<endl;
// for(ll x : s) cout<<x<< " "; cout<<endl;
for(ll j = 0;j<lg;j++){
asz = 0,bsz = 0;
for(ll i = 0;i<si(rut);i++){
if((1<<j)&i){
for(ll x : v[rut[i]]) a[asz++] = x;
}else{
for(ll x : v[rut[i]]) b[bsz++] = x;
}
}
// for(ll k = 0;k<asz;k++) cout<<a[k]<< " ";cout<<endl;
// for(ll k = 0;k<bsz;k++) cout<<b[k]<< " ";cout<<endl;
if(query(asz,bsz,a,b)){
ll tl = 0,tr = bsz-1,mid;
while(tl<tr){
mid = (tl+tr)/2;
csz = 0;
for(ll i = tl;i<=mid;i++) c[csz++] = b[i];
if(query(asz,csz,a,c)) tr = mid;
else tl = mid+1;
}
b[0] = b[tl];
bsz = 1;
tl = 0,tr = asz-1,mid;
while(tl<tr){
mid = (tl+tr)/2;
csz = 0;
for(ll i = tl;i<=mid;i++) c[csz++] = a[i];
if(query(csz,bsz,c,b)) tr = mid;
else tl = mid+1;
}
setRoad(b[0],a[tl]);
upd(b[0],a[tl]);
// cout<<"rod: "<<b[0]<< " "<<a[tl]<<endl;
break;
}
}
}
}
