#include <bits/stdc++.h>
#include "island.h"
using namespace std;
struct DSU
{
vector<int> dsu;
DSU(int n) : dsu(n+1, -1) { }
int get(int x) {
if(dsu[x] < 0) {
return x;
}
return get(dsu[x]);
}
bool merge(int x, int y) { // merge x to y
x = get(x), y = get(y);
if(x == y) {
return false;
}
dsu[y] += dsu[x];
dsu[x] = y;
return true;
}
};
void my_assert(bool x) {
if(!x) {
while(true) { }
}
}
void solve(int N, int L) {
vector<int> by_one {1}, order(N+1, -1);
order[1] = 0;
for(int i = 1; i < N; ++i) {
by_one.push_back(query(1, i));
// cerr << "Got: " << 1 << ' ' << i << ' ' << by_one.back() << '\n';
order[by_one.back()] = i;
}
for(int i = 1; i <= N; ++i) {
// cerr << order[i] << " \n"[i == N];
}
vector<int> par(N+1, -1);
DSU dsu(N);
for(int i = 2; i <= N; ++i) {
int cnt = 1;
while(par[i] == -1) {
const int x = query(i, cnt);
// cerr << "Got: " << i << ' ' << cnt << ' ' << x << '\n';
if(order[x] < order[i]) {
// assert(dsu.merge(i, x));
dsu.merge(i, x);
par[i] = x;
}
else {
// assert(dsu.merge(x, i));
dsu.merge(x, i);
par[x] = i;
}
cnt++;
}
}
for(int i = 2; i <= N; ++i) {
my_assert(par[i] != -1);
answer(i, par[i]);
}
}
