#include <bits/stdc++.h>

#ifndef LOCAL
#include "icc.h"
#endif

std::vector<std::vector<int>> gr;
std::vector<int> par;
std::vector<int> nodes;
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
// std::mt19937 rng(2);
int find(int a) {
    return par[a] < 0 ? a : par[a] = find(par[a]);
}

#ifdef LOCAL
namespace iv {
std::array<std::array<bool, 101>, 101> cc;
int na = -1, nb = -1;
int cnt = 0;
int num = 0;
int n;
} // namespace iv

int query(int a, int b, int *A, int *B) {
    ++iv::cnt;
    for (int ii = 0; ii < a; ++ii) {
        int i = A[ii];
        for (int jj = 0; jj < b; ++jj) {
            int j = B[jj];
            if (iv::cc[i][j]) {
                return true;
            }
        }
    }
    return false;
}
bool connected(int a, int b) {
    if (a == b) {
        return true;
    }
    if (par.empty()) {
        return false;
    }
    a = find(a);
    b = find(b);
    return a == b;
}
void newQuery() {
    while (true) {
        int a = (int)(rng() % iv::n + 1);
        int b = (int)(rng() % iv::n + 1);
        if (!connected(a, b)) {
            if (a > b) {
                std::swap(a, b);
            }
            iv::na = a;
            iv::nb = b;
            iv::cc[a][b] = true;
            iv::cc[b][a] = true;
            return;
        }
    }
}
void setRoad(int a, int b) {
    if (a > b) {
        std::swap(a, b);
    }
    ++iv::num;
    std::cerr << "Query " << iv::num << ":" << std::endl;
    std::cerr << "Your answer is: " << a << ' ' << b << std::endl;
    std::cerr << "The correct answer is: " << iv::na << ' ' << iv::nb
              << std::endl;
    std::cerr << std::endl;
    if (iv::na != a || iv::nb != b) {
        std::cerr << "Wrong Answer" << std::endl;
        std::exit(0);
    }
    if (iv::num < iv::n - 1) {
        newQuery();
    }
}
#endif

bool query(std::vector<int> &a, std::vector<int> &b) {
    if (a.empty() || b.empty()) {
        return false;
    }
    return query((int)a.size(), (int)b.size(), a.data(), b.data());
}
void unite(int a, int b) {
    int aa = a, bb = b;
    a = find(a);
    b = find(b);
    if (par[a] > par[b]) {
        std::swap(a, b);
    }
    gr[a].insert(gr[a].end(), gr[b].begin(), gr[b].end());
    gr[b].clear();
    par[a] += par[b];
    par[b] = a;
    setRoad(aa, bb);
}
void run(int N) {
    const int n = N;
    gr.resize(n + 1);
    for (int i = 1; i <= n; ++i) {
        gr[i].push_back(i);
    }
    nodes.resize(n);
    par.resize(n + 1, -1);
    std::iota(nodes.begin(), nodes.end(), 1);

    for (int i = 0; i < n - 1; ++i) {
        std::vector<int> a, b;
        while (true) {
            a.clear();
            b.clear();
            std::shuffle(nodes.begin(), nodes.end(), rng);
            for (int j = 0; j < n / 2; ++j) {
                a.insert(a.end(), gr[nodes[j]].begin(), gr[nodes[j]].end());
            }
            for (int j = n / 2; j < n; ++j) {
                b.insert(b.end(), gr[nodes[j]].begin(), gr[nodes[j]].end());
            }
            if (query(a, b)) {
                break;
            }
        }
        while ((int)a.size() > 1) {
            std::vector<int> na1(a.begin(), a.begin() + a.size() / 2),
                na2(a.begin() + a.size() / 2, a.end());
            if (query(na1, b)) {
                a = na1;
            } else {
                a = na2;
            }
        }
        while ((int)b.size() > 1) {
            std::vector<int> nb1(b.begin(), b.begin() + b.size() / 2),
                nb2(b.begin() + b.size() / 2, b.end());
            if (query(nb1, a)) {
                b = nb1;
            } else {
                b = nb2;
            }
        }
        unite(a[0], b[0]);
    }
}

#ifdef LOCAL
int main() {
    int n;
    std::cin >> n;
    iv::n = n;
    newQuery();
    run(n);
    std::cerr << "Number of queries used: " << iv::cnt << '\n';
}
#endif