#include <bits/stdc++.h>
#include "icc.h"
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define pb push_back
#define FIO ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0)
using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
const int N = 101;
int n;
int a[N], b[N], par[N], siz[N];
vector <int> c[N];
int find(int x) {return x == par[x] ? x : (par[x] = find(par[x]));}
void unite(int x, int y) {
x = find(x);
y = find(y);
if (siz[x] < siz[y]) swap(x, y);
par[y] = x;
siz[x] += siz[y];
for (auto it : c[y]) c[x].pb(it);
}
pii f(vector <int> v) {
// for (auto it : v) cout << it << " "; cout << "F" << endl;
vector <int> g, h;
int sa, sb;
pii p;
vector <int> wh(n+1);
int e = 0;
for (int i = 10; i >= 0; i--) if ((1 << i) < v.size()) {
sa = 0; sb = 0;
for (int j = 0; j < v.size(); j++) {
if (j & (1 << i)) for (int x : c[v[j]]) b[sb++] = x, wh[x] = j;
else for (int x : c[v[j]]) a[sa++] = x, wh[x] = j;
}
// for (int j = 0; j < sa; j++) cout << a[j] << " "; cout << "| ";
// for (int j = 0; j < sb; j++) cout << b[j] << " "; cout << "\n";
if (query(sa, sb, a, b)) {
for (int i = 0; i < sa; i++) g.pb(a[i]);
for (int i = 0; i < sb; i++) h.pb(b[i]);
e = i;
break;
}
}
// cout << "CP1 " << g.size() << " " << h.size() << endl;
sb = 0;
for (int i = 0; i < h.size(); i++) b[sb++] = h[i];
int lo = 0, hi = g.size()-1;
while (lo < hi) {
int mid = (lo+hi)/2;
sa = 0;
for (int i = 0; i <= mid; i++) a[sa++] = g[i];
// for (int j = 0; j < sa; j++) cout << a[j] << " "; cout << "| ";
// for (int j = 0; j < sb; j++) cout << b[j] << " "; cout << "\n";
if (query(sa, sb, a, b)) hi = mid;
else lo = mid+1;
}
p.F = g[lo];
// cout << p.F << " " << wh[p.F] << "\n";
vector <int> hh;
for (int x : h) {
if (wh[x]/(1<<e+1) == wh[p.F]/(1<<e+1)) hh.pb(x);
// cout << wh[x] << " ";
}
// cout << " h\n";
swap(h, hh);
// for (auto it : h) cout << it << " "; cout << "\n";
// cout << "CP2 " << g.size() << " " << h.size() << endl;
sa = 0;
for (int i = 0; i < g.size(); i++) a[sa++] = g[i];
lo = 0, hi = h.size()-1;
while (lo < hi) {
int mid = (lo+hi)/2;
sb = 0;
for (int i = 0; i <= mid; i++) b[sb++] = h[i];
// for (int j = 0; j < sa; j++) cout << a[j] << " "; cout << "| ";
// for (int j = 0; j < sb; j++) cout << b[j] << " "; cout << "\n";
if (query(sa, sb, a, b)) hi = mid;
else lo = mid+1;
}
// cout << "END\n";
p.S = h[lo];
return p;
}
void run(int nn) {
n = nn;
vector <int> v;
for (int i = 1; i <= n; i++) v.pb(i), c[i].pb(i), par[i] = i, siz[i] = 1;
for (int ii = 1; ii < n; ii++) {
pii p = f(v);
// cout << "ANS " << p.F << " " << p.S << endl;
setRoad(p.F, p.S);
unite(p.F, p.S);
v.clear();
for (int i = 1; i <= n; i++) v.pb(find(i));
sort(all(v));
v.erase(unique(all(v)), v.end());
// for (auto it : v) cout << it << " "; cout << " x\n";
}
}
