//test
#include <bits/stdc++.h>
using namespace std;
#include "tree.h"

namespace flower {
	constexpr int N = 1010;
	bitset<N> G[N], vis[N];
	int tot;
	int ask(int x, int y) {
		if(x == y) return 1;
		if(x > y) swap(x, y);
		if(vis[x][y]) return G[x][y];
		vis[x][y] = 1;
		G[x][y] = Query({x, y}) == 2;
		tot ++;
		return G[x][y];
	}
	int use[N], bel[N], cnt[N];
	void solve(int n) {
		vector<vector<int>> tree;
		vector<int> fa, dep, kth;
		int tot = n;
		mt19937 hua(20000724);
		vector<int> ord(n);
		iota(ord.begin(), ord.end(), 1);
		shuffle(ord.begin(), ord.end(), hua);
		for(auto i : ord) if(!use[i]) {
			vector<int> chain;
			chain.emplace_back(i);
			auto tryins = [&] (int x) {
				int B = 50;
				for(auto y : chain) {
					if(!--B) return true;
					if(!ask(x, y)) return false;
				}
				return true;
			};
			for(int j = 1; j <= n; j ++) if(j != i && !use[j]) {
				if(tryins(j)) {
					chain.emplace_back(j);
				}
				if(tot > 1e5) {
					Report(-1, -1);
					return ;
				}
			}
			int curdep = 0;
			int id = tree.size();
			tree.emplace_back(chain);
			fa.emplace_back(-1);
			kth.emplace_back();
			for(int j = 1; j <= n; j ++) if(use[j] && dep[bel[j]] > curdep) {
				if(tryins(j)) {
					curdep = dep[bel[j]];
					fa.back() = bel[j];
				}
			}
			dep.emplace_back(curdep + 1);
			for(auto x : chain) bel[x] = id, use[x] = 1;
			for(int j = 1; j <= n; j ++) if(use[j] && bel[j] == fa.back()) {
				if(tryins(j)) {
					cnt[j] ++;
					kth.back() ++;
				}
			}
		}
		vector<vector<int>> G(tree.size());
		for(int i = 0; i < tree.size(); i ++) if(fa[i] != -1) {
			G[fa[i]].emplace_back(i);
		}
		vector<pair<int, int>> edge;
		for(int i = 0; i < tree.size(); i ++) {
			sort(tree[i].begin(), tree[i].end(), [&] (int x, int y){return cnt[x] > cnt[y];});
			for(int j = 1; j < tree[i].size(); j ++) {
				if(cnt[tree[i][j]] == cnt[tree[i][j - 1]]) {
					Report(-1, -1);
					return ;
				}
				edge.emplace_back(tree[i][j], tree[i][j - 1]);
			}
			if(fa[i] != -1) {
				edge.emplace_back(tree[i][0], tree[fa[i]][kth[i] - 1]);
			}
		}
		assert(edge.size() == n - 1);
		for(auto [u, v] : edge) {
			Report(v, u);
		}
	}
}
void Solve(int N) {
	return flower::solve(N);
}