#include "island.h"
#include <vector>
using namespace std;
void solve(int N, int L) {
// Phase 1: Get all islands sorted by distance from island 1
vector<int> A(N);
A[0] = 1;
for (int i = 1; i < N; ++i) {
A[i] = query(1, i);
}
// pos[i] will store the topological position of island i
vector<int> pos(N + 1);
for (int i = 0; i < N; ++i) {
pos[A[i]] = i;
}
// To skip redundant querying if a child was already explored by its parent
vector<bool> parent_known(N + 1, false);
parent_known[1] = true; // island 1 is the root, has no parent
// Phase 2: Build the tree edges
for (int i = 1; i < N; ++i) {
int v = A[i];
// If v was already found by its parent, we skip it
if (parent_known[v]) {
continue;
}
int idx = 1;
while (true) {
int u = query(v, idx++);
if (pos[u] < pos[v]) {
// `u` appeared before `v`, meaning `u` is the parent of `v`.
// Edge safely found, stop querying `v`!
answer(v, u);
break;
} else {
// `u` appeared after `v`, meaning `u` is a child of `v`.
// Log the edge and register `u` so we skip it later.
answer(v, u);
parent_known[u] = true;
}
}
}
}
