#include<bits/stdc++.h>
#include "icc.h"
using namespace std;
#define ii pair <int, int>
#define app push_back
#define all(a) a.begin(), a.end()
#define bp __builtin_popcount
#define ll long long
#define mp make_pair
#define f first
#define s second
const int N = 101;
mt19937 rnd(time(0));
int ar[N], br[N];
bool quer(vector <int> a, vector <int> b) {
    if (a.empty() || b.empty()) return 0;
    for (int i = 0; i < a.size(); ++i) ar[i] = a[i] + 1;
    for (int i = 0; i < b.size(); ++i) br[i] = b[i] + 1;
    return query(a.size(), b.size(), ar, br);
}
ii get(vector <int> a, vector <int> b) {
    if (a.size() == 1 && b.size() == 1) return {a[0], b[0]};
    if (a.size() == 1) swap(a, b);
    vector <int> l, r;
    int m = a.size() / 2;
    for (int i = 0; i < m; ++i) l.app(a[i]);
    for (int i = m; i < (int)a.size(); ++i) r.app(a[i]);
    if (quer(l, b)) return get(l, b);
    else return get(r, b);
}
vector <int> a[N];
int c[N];
void run(int n) {
    for (int i = 0; i < n; ++i) { a[i].app(i); c[i] = i; }
    for (int e = 0; e < n - 1; ++e) {
        while (1) {
            vector <int> l, r;
            for (int i = 0; i < n; ++i) {
                if (rnd() & 1) { for (int e : a[i]) l.app(e); }
                else { for (int e : a[i]) r.app(e); }
            }
            if (quer(l, r)) {
                ii ans = get(l, r);
                setRoad(ans.first + 1, ans.second + 1);
                int c1 = c[ans.first], c2 = c[ans.second];
                for (int e : a[c2]) { a[c1].app(e); c[e] = c1; }
                a[c2].clear();
                break;
            }
        }
    }
}