#include <bits/stdc++.h>
#include "island.h"
using i64 = long long;
#ifdef DEBUG
#include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
#define debug(...) void(23)
#endif
namespace {
int N;
}
std::map<std::pair<int, int>, int> save;
int ask(int v, int k) {
assert(0 <= v && v < N && 1 <= k && k < N);
if (save.contains({v, k})) {
return save[{v, k}];
}
return save[{v, k}] = query(v + 1, k) - 1;
}
void solve(int N, int L) {
::N = N;
// int variable_example = query(1, 1);
// for (int i = 2; i <= N; i++) {
// answer(1, i);
// }
std::vector<int> vis(N), lst(N, -1);
std::vector<int> cur(N, 1), par(N, -1);
std::vector<std::map<int, int>> idx(N);
std::vector<int> stk {0};
std::vector<std::pair<int, int>> ans;
vis[0] = true;
while (ans.size() != N - 1) {
int v = stk.back();
debug(stk);
if (cur[v] == N) {
stk.pop_back();
continue;
}
debug(v, cur[v]);
int u = ask(v, cur[v]);
idx[v][u] = cur[v];
cur[v]++;
debug(u);
if (u < lst[v]) {
stk.pop_back();
continue;
} else if (vis[u]) {
if (u == par[v]) {
continue;
} else {
debug("pop", v);
stk.pop_back();
continue;
}
} else if (v != 0) {
// check is it connected to me?
int p = par[v], stp = cur[u];
while (!idx[u].contains(p) && !idx[u].contains(v)) {
int x = ask(u, cur[u]);
debug(u, cur[u], x);
idx[u][x] = cur[u];
cur[u]++;
}
cur[u] = stp;
if (idx[u].contains(v) && idx[u].contains(p)) {
if (idx[u][p] < idx[u][v]) {
debug("leaf", v);
stk.pop_back();
continue;
}
} else if (idx[u].contains(p)) {
debug("leaf", v);
stk.pop_back();
continue;
}
}
debug(v, u);
vis[u] = true;
par[u] = v;
lst[v] = u;
ans.emplace_back(v, u);
stk.emplace_back(u);
}
for (auto[u, v] : ans) {
answer(u + 1, v + 1);
}
}
