#include "island.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<int> par;
vector<set<int>> ch;
int get_par(int node) {
vector<int> allCh;
for (auto nxt: ch[node]) allCh.push_back(nxt);
int tot = allCh.size();
allCh.push_back(-1);
sort(allCh.begin(), allCh.end());
if (tot == 0) {
return query(node, 1);
}
int lo = 1, hi = tot+1;
while (lo <= hi) {
int mid = (lo + hi) / 2;
int ans = query(node, mid);
if (ch[node].find(ans) == ch[node].end()) return ans;
if (ans == allCh[mid]) {
lo = mid+1;
}
else {
hi = mid-1;
}
}
assert(false);
}
void solve(int N, int L) {
n = N;
par.assign(n+1, -1);
ch.resize(n+1);
int root = 1;
for (int i = n-1; i >= 2; i--) {
int nxt = query(root, i);
par[nxt] = get_par(nxt);
ch[par[nxt]].insert(nxt);
answer(par[nxt], nxt);
}
answer(root, query(root, 1));
}
