#include "bits/stdc++.h"
#include "icc.h"
using namespace std;

struct dsu {
    vector<int> p;
    vector<vector<int>> d;

    dsu(int n) {
        p.resize(n);
        d.resize(n);
        for (int i = 0; i < n; i++) {
            p[i] = i;
            d[i] = {i};
        }
    }

    int get(int u) {
        if (u == p[u]) {
            return u;
        } else {
            return p[u] = get(p[u]);
        }
    }

    void join(int u, int v) {
        u = get(u);
        v = get(v);
        if (u == v) {
            return;
        }
        if (d[v].size() > d[u].size()) {
            swap(u, v);
        }
        p[v] = u;
        d[u].insert(d[u].end(), d[v].begin(), d[v].end());
        d[v].clear();
    }
};

void run(int n) {
    dsu Q(n + 1);
    int cnt = 0;
    for (int u = 1; u <= n && cnt != n - 1; u++) {
        for (int v = 1; v <= n && cnt != n - 1; v++) {
            if (Q.get(u) != Q.get(v)) {
                if (query(1, 1, &u, &v)) {
                    setRoad(u, v);
                    Q.join(u, v);
                    cnt++;
                }
            }
        }
    }
}