#include <bits/stdc++.h>
#include "icc.h"
using namespace std;
#define endl "\n"
#define pii pair<int, int>
#define piv pair<int, vector<pii>>
class DSU {
public:
vector<int> parents;
vector<int> sizes;
int comp;
DSU(int size) : parents(size), sizes(size, 1) {
for (int i = 0; i < size; i++) { parents[i] = i; }
comp = size;
}
/** @return the "representative" node in x's component */
int find(int x) { return parents[x] == x ? x : (parents[x] = find(parents[x])); }
/** @return whether the merge changed connectivity */
bool unite(int x, int y) {
comp--;
int x_root = find(x);
int y_root = find(y);
if (x_root == y_root) { return false; }
if (sizes[x_root] < sizes[y_root]) { swap(x_root, y_root); }
sizes[x_root] += sizes[y_root];
parents[y_root] = x_root;
return true;
}
/** @return whether x and y are in the same connected component */
bool connected(int x, int y) { return find(x) == find(y); }
};
void run(int n){
DSU dsu(n);
for(int step = 1; step < n; step++){
int c = 0;
map<int, int> mp;
vector<vector<int>> connected_comp;
for(int i = 0; i < n; i++){
if(mp.count(dsu.find(i))){
connected_comp[mp[dsu.find(i)]].push_back(i);
}
else{
connected_comp.push_back({i});
mp[dsu.find(i)] = c++;
}
}
vector<int> endpoints;
for(int i = 0; i < dsu.comp; i++){
int rest[n - connected_comp[i].size()];
int cc = 0;
for(int j = 0; j < dsu.comp; j++){
if(j == i) continue;
for(auto e: connected_comp[j]) rest[cc++] = e + 1;
}
for(auto e: connected_comp[i]){
int q = query(1, n - connected_comp[i].size(), new int[]{e + 1}, rest);
if(q == 1){
endpoints.push_back(e);
}
}
}
setRoad(endpoints[0] + 1, endpoints[1] + 1);
dsu.unite(endpoints[0], endpoints[1]);
}
}
