#include <bits/stdc++.h>
using namespace std;
#include "island.h"
#define vc vector<char>
#define vi vector<int>
#define vii vector<vi>
#define viii vector<vii>
#define viiii vector<viii>
#define viiiii vector<viiii>
#define vb vector<bool>
#define pi pair<double, double>
void dfs(int v, int p, vb& vis, vii& adj, bool& res) {
if (vis[v]) { res = 1; return; }
vis[v] = 1;
for (int to : adj[v]) {
if (to == p) continue;
dfs(to, v, vis, adj, res);
}
}
bool hasCycle(vii& adj) {
int n = adj.size()-1;
bool res = 0;
vb vis(n+1, 0);
for (int v = 1; v <= n; v++) {
if (!vis[v]) dfs(v, -1, vis, adj, res);
}
return res;
}
void solve(int n, int L) {
vb sol(n+1, 0);
vector<vb> edge(n+2, vb(n+2, 0));
vii adj(n+1);
auto addEdge = [&](int a, int b) {
if (edge[a][b]) return;
adj[a].push_back(b);
adj[b].push_back(a);
edge[a][b] = edge[b][a] = 1;
answer(a, b);
};
for (int v = n; v >= 1; v--) {
int sum = 0;
for (int x : sol) sum += x;
if (sum == n-1) break;
if (sol[v]) {
for (int q : adj[v]) {
if (q > v) continue;
if (sol[q]) continue;
for (int k2 = 1; k2 < n; k2++) {
int q2 = query(q, k2);
if (q2 >= v) break;
addEdge(q, q2);
}
sol[q] = 1;
}
continue;
}
for (int k = 1; k < n; k++) {
int q = query(v, k);
if (!edge[v][q]) {
adj[v].push_back(q);
adj[q].push_back(v);
bool b = hasCycle(adj);
adj[v].pop_back();
adj[q].pop_back();
if (b) break;
}
if (q > v) break;
if (sol[q]) continue;
addEdge(v, q);
for (int k2 = 1; k2 < n; k2++) {
int q2 = query(q, k2);
if (q2 >= v) break;
addEdge(q, q2);
}
sol[q] = 1;
}
sol[v] = 1;
}
}
