#include "island.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> par;
vector<set<int>> ch;
int get_par(int node) {
for (int i = 1; i <= n-1; i++) {
int nxt = query(node, i);
if (ch[node].find(nxt) == ch[node].end()) return nxt;
}
assert(false);
}
void solve(int N, int L) {
n = N;
par.assign(n+1, -1);
ch.resize(n+1);
int root = 1;
queue<int> q;
vector<bool> done(n+1, false);
for (int i = n-1; i >= 2; i--) {
int nxt = query(root, i);
if (done[nxt]) break;
par[nxt] = get_par(nxt);
ch[par[nxt]].insert(nxt);
answer(par[nxt], nxt);
done[nxt] = true;
done[par[nxt]] = true;
if (par[nxt] != root) q.push(par[nxt]);
}
while (!q.empty()) {
int nxt = q.front();
q.pop();
if (nxt == root || done[nxt]) continue;
par[nxt] = get_par(nxt);
ch[par[nxt]].insert(nxt);
answer(par[nxt], nxt);
done[nxt] = true;
done[par[nxt]] = true;
if (par[nxt] != root) q.push(par[nxt]);
}
for (int i = 2; i <= n; i++) {
if (par[i] == -1) {
answer(root, i);
return;
}
}
}
