#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();
    }
};

mt19937 rnd(228);

int rand(int n) {
    return rnd() % n;
}

int rand(int l, int r) {
    return l + rand(r - l + 1);
}

vector<int> low_half(vector<int> A) {
    if (A.size() == 1) {
        return A;
    }
    int x = A.size() >> 1;
    return vector<int>(A.begin(), A.begin() + x);
}

vector<int> top_half(vector<int> A) {
    if (A.size() == 1) {
        return A;
    }
    int x = A.size() >> 1;
    return vector<int>(A.begin() + x, A.end());
}

int query(vector<int> A, vector<int> B) {
    return query(A.size(), B.size(), A.data(), B.data());
}

void run(int n) {
    dsu Q(n + 1);

    auto loop = [&]() {
        vector<int> a;
        vector<int> b;
        while (true) {
            a.clear();
            b.clear();

            for (int u = 1; u <= n; u++) {
                if (Q.get(u) == u && rand(2)) {
                    a.insert(a.end(), Q.d[u].begin(), Q.d[u].end());
                } else {
                    b.insert(b.end(), Q.d[u].begin(), Q.d[u].end());
                }
            }
            if (a.empty() || b.empty()) {
                continue;
            }
            if (query(a, b)) {
                break;
            }
        }

        while (a.size() != 1 || b.size() != 1) {
            if (query(low_half(a), low_half(b))) {
                a = low_half(a);
                b = low_half(b);
            }
            
            else if (query(low_half(a), top_half(b))) {
                a = low_half(a);
                b = top_half(b);
            }

            else if (query(top_half(a), low_half(b))) {
                a = top_half(a);
                b = low_half(b);
            }

            else {
                a = top_half(a);
                b = top_half(b);
            }
        }

        setRoad(a.front(), b.front());
        Q.join(a.front(), b.front());
    };

    for (int i = 0; i < n - 1; i++) {
        loop();
    }
}

#ifdef LOCAL
int main() {
    int n;
    cin >> n;
    run(n);
}
#endif