#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;
}
bool contains(vi& v, int x) {
for (int p : v) {
if (p == x) return 1;
}
return 0;
}
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) {
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);
};
for (int v = 1; v <= n-1; v++) {
int c = adj[v].size();
bool first = 1;
for (int k = c+1; k < n; k++) {
if (cnt == n-1) break;
int q = query(v, k);
if (first) {
bool b = 0;
for (int to : adj[v]) {
b |= contains(adj[to], q);
}
if (b) break;
addEdge(v, q);
first = 0;
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;
int q2 = query(q, adj[q].size()+1);
addEdge(q, q2);
if (q2 != v || cnt == n-1) {
break;
}
}
if (cnt == n-1) break;
}
}
