#include "island.h"
#include<bits/stdc++.h>

using namespace std;

typedef int ll;

map<pair<ll, ll>, ll> mind;

ll get(ll x, ll y) {
	if (mind.find(make_pair(x, y)) != mind.end()) {
		return mind[make_pair(x, y)];
	}
	return mind[make_pair(x, y)] = query(x + 1, y + 1) - 1;
}

void ans(ll x, ll y) {
	answer(x + 1, y + 1);
}

struct DSU {
	vector<ll> p;
	DSU(ll n) {
		p.resize(n);
		for (ll i = 0; i < n; i++) {
			p[i] = i;
		}
	}
	ll get(ll v) {
		return (v == p[v] ? v : p[v] = get(p[v]));
	}
	bool unite(ll a, ll b) {
		a = get(a);
		b = get(b);
		if (a == b) {
			return false;
		}
		p[a] = b;
		return true;
	}
};

void solve(ll n, ll l) {
	vector<vector<ll>> to(n);
	vector<ll> col(n, 0);
	ll ost = n - 1;
	DSU d(n);
	for (ll i = 0; i < n; i++) {
		ll start = 0;
		for (auto j : to[i]) {
			if (j < i) {
				start++;
			}
		}
		while (start < n - 1 && start < 2 && ost > 0) {
			ll x = get(i, start);
			if (d.get(x) == d.get(i)) {
				break;
			}
			if (x < i) {
				break;
			}
			if (get(x, col[x]) == i) {
				col[x]++;
				ost--;
				to[i].push_back(x);
				to[x].push_back(i);
				d.unite(x, i);
			} else {
				break;
			}
			start++;
		}
	}
	for (ll i = 0; i < n; i++) {
		for (auto j : to[i]) {
			if (j > i) {
				ans(i, j);
			}
		}
	}
}