#include "island.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int; using pii = pair<ll,ll>;
const ll Nm = 305;
ll f[Nm];
// void answer(ll x, ll y) {
// cout << x << " " <<y << "\n";
// }
// //7 4 1 6 3 2 5
// vector<pii> edges = {{6,3},{3,0},{0,5},{5,2},{2,1},{1,4}};
// ll N1 = 7;
// ll query(ll x, ll d) {
// cout << "call query(x="<<x<<",d="<<d<<")\n";
// x--; d--;
// vector<ll> dist(Nm,-1);
// dist[x]=0;
// while(1) {
// bool df = 0;
// for (pii p0: edges) {
// if (dist[p0.first]==-1 && dist[p0.second]!=-1) {
// dist[p0.first]=1+dist[p0.second];
// df = 1;
// }
// if (dist[p0.first]!=-1 && dist[p0.second]==-1) {
// dist[p0.second]=1+dist[p0.first];
// df = 1;
// }
// }
// if (!df) {
// break;
// }
// }
// vector<pii> vc;
// for (ll i=0;i<N1;i++) {
// if (i!=x) {
// vc.push_back({dist[i],i});
// }
// }
// sort(vc.begin(),vc.end());
// cout << "returning "<<(vc[d].second+1)<<"\n";
// return (vc[d].second+1);
// }
ll getf(ll x) {
if (f[x]==x) {
return x;
}
return (f[x]=getf(f[x]));
}
void fz(ll a, ll b) {
a = getf(a); b = getf(b);
f[a]=b;
}
set<pii> sans;
void ANS(ll a, ll b) {
if (sans.find({a,b})!=sans.end()) {
return;
}
sans.insert({a,b});
sans.insert({b,a});
answer(a+1,b+1);
fz(a,b);
}
void solve(int N, int L) {
for (ll i=0;i<N;i++) {
f[i]=i;
}
ll x0[N];
for (ll i=0;i<N;i++) {
x0[i]=query(i+1,1)-1;
}
vector<bool> frz(N,0); //frozen?
vector<bool> o2(N,0); //only round 2?
vector<bool> odn(N,0);
for (ll i=0;i<N;i++) {
ANS(i,x0[i]);
if (x0[x0[i]]==i) {
if (i<x0[i]) {
frz[i]=1;
//cout << "FREEZE i="<<i<<"\n";
odn[x0[i]]=1;
}
} else if (x0[i]>i) {
//o2[i]=1;
frz[i]=1;
//cout << "FREEZE i="<<i<<"\n";
}
}
for (int i=0;i<N;i++) {
if (x0[i]>i && x0[x0[i]]!=i) {
odn[x0[i]]=1;
}
}
for (ll T=2;T<N;T++) {
for (ll i=(N-1);i>=0;i--) {
if (!frz[i] || (T==2 && o2[i])) {
ll j = query(i+1,T)-1;
if (odn[i] && j>i) {
frz[i]=1;
//cout << "FREEZE i="<<i<<"\n";
continue;
}
if (getf(i)!=getf(j)) {
ANS(i,j);
} else {
if (sans.find({i,j})==sans.end()) {
frz[i]=1;
//cout << "FREEZE i="<<i<<"\n";
}
}
if (j>i) {
frz[i]=1;
//cout << "FREEZE i="<<i<<"\n";
}
}
}
}
}
