#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);
int cnt = 0;
auto addEdge = [&](int a, int b) {
// cerr << a << ' ' << b << endl;
if (edge[a][b]) return;
adj[a].push_back(b);
adj[b].push_back(a);
edge[a][b] = edge[b][a] = 1;
cnt++;
answer(a, b);
};
vi hi(n+1, 0);
for (int v = 1; v <= n; v++) {
int c = hi[v];
for (int to : adj[v]) {
if (to > v) hi[to]++;
}
bool first = 1;
for (int k = c+1; k < n; k++) {
int q = query(v, k);
if (k == 1) { addEdge(v, q); hi[q]++; continue; }
if (edge[v][q]) continue;
adj[q].push_back(v);
adj[v].push_back(q);
bool b = hasCycle(adj);
adj[q].pop_back();
adj[v].pop_back();
if (q < v || b) break;
if (first) {
addEdge(v, q);
first = 0;
continue;
}
int q2 = query(q, hi[q]+1);
addEdge(q, q2);
if (q2 == v) hi[q]++;
else break;
}
}
}
