#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define pb push_back
#define sz(a) (int)a.size()
#define all(a) begin(a),end(a)
using vi = vector<int>;
using ar2 = array<int,2>;
template<int SZ> struct Dsu{
int p[SZ]; vi v[SZ];
set<int> comps;
void init(int n){
comps.clear();
for(int i = 1; i <= n; i++){
v[i].clear(); v[i].pb(i);
p[i]=i, comps.insert(i);
}
}
int findSet(int i){ return i==p[i]?i:p[i]=findSet(p[i]); }
bool isSameSet(int i, int j){ return findSet(i)==findSet(j); }
void unionSet(int i, int j){
int x = findSet(i), y = findSet(j);
if(x==y) return;
if(sz(v[x])<sz(v[y])) swap(x,y);
p[y]=x; for(auto u : v[y]) v[x].pb(u);
v[y].clear(); v[y].shrink_to_fit(); comps.erase(y);
}
};
Dsu<101> dsu;
bool query(vi V, vi W){
int n = sz(V), m = sz(W); int v[n], w[m];
for(int i = 0; i < n; i++) v[i]=V[i];
for(int i = 0; i < m; i++) w[i]=W[i];
return query(n,m,v,w);
}
bool Query(vi V, vi W){
vi v, w; v.clear(); w.clear();
for(auto u : V) for(auto x : dsu.v[u]) v.pb(x);
for(auto u : W) for(auto x : dsu.v[u]) w.pb(x);
return min(sz(v),sz(w))?query(v,w):0;
}
ar2 solve(vi V, vi W){
vi v, w; v.clear(); w.clear();
for(auto u : V) for(auto x : dsu.v[u]) v.pb(x);
for(auto u : W) for(auto x : dsu.v[u]) w.pb(x);
int x, y, l, r;
l = 0, r = sz(v)-1;
while(l<r){
int mid = (l+r)/2; vi vv; vv.clear();
for(int i = 0; i <= mid; i++) vv.pb(v[i]);
if(query(vv,w)) r=mid;
else l=mid+1;
}
x = v[l];
l = 0, r = sz(w)-1;
while(l<r){
int mid = (l+r)/2; vi ww; ww.clear();
for(int i = 0; i <= mid; i++) ww.pb(w[i]);
if(query({x},ww)) r=mid;
else l=mid+1;
}
y = w[l];
return {x,y};
}
void run(int n){
dsu.init(n); srand(time(0));
for(int _ = 1; _ < n; _++){
int num_comps = sz(dsu.comps);
bool ok = 0; vi t[2];
for(int j = 0; j < __lg(num_comps-1); j++){
t[0].clear(); t[1].clear();
auto itr = begin(dsu.comps);
for(int i = 0; i < num_comps; i++)
t[i>>j&1].pb(*itr), itr++;
if(Query(t[0],t[1])) { ok=1; break; }
}
if(!ok){
int j = __lg(num_comps-1);
t[0].clear(); t[1].clear();
auto itr = begin(dsu.comps);
for(int i = 0; i < num_comps; i++)
t[i>>j&1].pb(*itr), itr++;
ok = 1;
}
auto [x,y] = solve(t[0],t[1]);
setRoad(x,y); dsu.unionSet(x,y);
}
}
