#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
#include "icc.h"
#define ll long long
#define ui unsigned int
#define pii pair<int, int>
#define pis pair<int, string>
#define piii pair<int, pii>
#define pb push_back
#define f first
#define s second
#define oo (1ll << 60)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct DSU {
vector<int>root;
vector<vector<int>>group;
DSU(int n) {
group.resize(n + 1);
root.resize(n + 1);
for(int i = 1; i <= n; ++i) {
group[i].clear();
group[i].pb(i);
root[i] = i;
}
}
void Union(int u, int v) {
u = root[u];
v = root[v];
if(group[u].size() < group[v].size()) {
swap(u, v);
}
for(int node : group[v]) {
root[node] = u;
group[u].pb(node);
}
group[v].clear();
}
};
void solve(int &size_a, int size_b, int a[], int b[]) {
if(size_a > 1) {
if(query(size_a / 2, size_b, a, b)) {
size_a /= 2;
}else {
int pos = 0;
for(int i = size_a / 2; i < size_a; ++i) {
a[pos++] = a[i];
}
size_a = pos;
}
solve(size_a, size_b, a, b);
}
}
const int SIZE = 101;
int Query(vector<int> &roots_a, vector<int> &roots_b, DSU &dsu) {
int a[SIZE], b[SIZE];
int size_a = 0, size_b = 0;
for(int r : roots_a) {
if(r == 0) continue;
for(int node : dsu.group[r]) {
a[size_a++] = node;
}
}
for(int r : roots_b) {
if(r == 0) continue;
for(int node : dsu.group[r]) {
b[size_b++] = node;
}
}
if(query(size_a, size_b, a, b)) {
solve(size_a, size_b, a, b);
solve(size_b, size_a, b, a);
setRoad(a[0], b[0]);
dsu.Union(a[0], b[0]);
return 1;
}else {
return 0;
}
}
void solve(int n, DSU &dsu) {
vector<int>roots_a, roots_b;
int pw = 1;
for(int i = 1; i <= n; ++i) {
if(dsu.root[i] == i) {
if(roots_a.size() <= roots_b.size()) {
roots_a.pb(i);
}else {
roots_b.pb(i);
}
if(pw < (int)roots_a.size()) pw <<= 1;
}
}
int res = 0;
int sza = (int)roots_a.size();
int szb = (int)roots_b.size();
while(sza <= pw) {
roots_a.pb(0);
++sza;
}
while(szb <= pw) {
roots_b.pb(0);
++szb;
}
for(int i = 1; !res; i *= 2) {
int jump = sza / i;
int pos = jump;
while(pos < sza && pos < szb) {
swap(roots_a[pos], roots_b[pos]);
++pos;
if(pos % jump == 0) pos += jump;
}
res = Query(roots_a, roots_b, dsu);
}
}
void run(int n) {
DSU dsu(n);
for(int i = 1; i < n; ++i) {
solve(n, dsu);
}
}
