#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
struct Comp{
vector<int> nodes;
};
vector<vector<int>> tree;
vector<bool> vis;
void dfs(int v, vector<int> &vec){
vis[v] = true;
vec.push_back(v);
for(auto e : tree[v]){
if(!vis[e]) dfs(e, vec);
}
}
void run(int n){
tree.assign(n + 1, {});
int mx = 0;
for(int it = 0; it <= n - 1; it++){
int s, t;
vector<Comp> comps;
vis.assign(n + 1, false);
for(int v = 1; v <= n; v++){
if(!vis[v]){
Comp tmp;
comps.push_back(tmp);
dfs(v, comps.back().nodes);
}
}
vector<int> a, b, c;
for(int k = 0; k < 7; k++){
a.clear(), b.clear();
for(int i = 0; i < comps.size(); i++){
if(i & (1 << k)) for(auto v : comps[i].nodes) a.push_back(v);
else for(auto v : comps[i].nodes) b.push_back(v);
}
if(query(a.size(), b.size(), a.data(), b.data())) break;
}
shuffle(a.begin(), a.end(), rng);
shuffle(b.begin(), b.end(), rng);
int l = -1, r = a.size() - 1, m;
while(r - l > 1){
m = l + (r - l) / 2;
c.clear();
for(int i = 0; i <= m; i++) c.push_back(a[i]);
if(query(c.size(), b.size(), c.data(), b.data())) r = m;
else l = m;
}
s = a[r];
l = -1, r = b.size() - 1;
while(r - l > 1){
m = l + (r - l) / 2;
c.clear();
for(int i = 0; i <= m; i++) c.push_back(b[i]);
if(query(c.size(), a.size(), c.data(), a.data())) r = m;
else l = m;
}
t = b[r];
setRoad(s, t);
tree[s].push_back(t);
tree[t].push_back(s);
}
}
