#include "island.h"
#include <bits/stdc++.h>
using namespace std;
vector<pair<int, int>> a;
int f[300][300], tr[300][300];
int dp(int l, int r){
if (l>r) return 0;
if (f[l][r]!=-1) return f[l][r];
if (l==r && a[l].second==1){
tr[l][r]=-1;
return f[l][r]=0;
}
pair<int, int> res={(int)1e9, -1};
for (int j=l; j<=r; ++j){
res=min(res, {1+max(dp(l, j-1), dp(j+1, r)), j});
}
tr[l][r]=res.second;
return f[l][r]=res.first;
}
void solve(int _N, int _L) {
int query_count=0;
mt19937 rng(69420);
int n=_N;
int root=0;
vector<int> bfs_order{root}, pos(n);
for (int i=1; i<n; ++i) bfs_order.push_back(query(root+1, i)-1), ++query_count;
for (int i=0; i<n; ++i) pos[bfs_order[i]]=i;
vector<vector<int>> child(n);
vector<int> par(n);
vector<int> check(n);
for (int i=n-1; i>=1; --i){
int u=bfs_order[i];
sort(child[u].begin(), child[u].end());
for (int j:child[u]) check[j]=1;
vector<int> cnt(child[u].size()+1), save(child[u].size()+1);
for (int j=0; j<i; ++j){
int v=bfs_order[j];
int t=lower_bound(child[u].begin(), child[u].end(), v)-child[u].begin();
++cnt[t];
save[t]=v;
}
a.clear();
for (int j=0; j<=(int)child[u].size(); ++j) if (cnt[j]){
a.emplace_back(j, cnt[j]);
}
for (int j=0; j<=(int)child[u].size(); ++j) for (int k=0; k<=(int)child[u].size(); ++k){
f[j][k]=-1;
}
dp(0, (int)a.size()-1);
cerr << query_count << endl;
if (query_count==638){
query_count=638;
}
int l=0, r=a.size()-1;
while (1){
int mid=tr[l][r];
int v=-1;
if (l==r && f[l][r]==0){
v=save[a[l].first];
}else{
v=query(u+1, a[mid].first+1)-1, ++query_count;
}
if (!check[v]){
par[u]=v;
child[v].push_back(u);
break;
}
if (child[u][a[mid].first]==v) l=mid+1;
else r=mid-1;
}
for (int j:child[u]) check[j]=0;
}
for (int i=0; i<n; ++i) if (i!=root) answer(i+1, par[i]+1);
}
