#include<bits/stdc++.h>
#include"tree.h" 
#define L(i, j, k) for(int i = (j); i <= (k); ++i)
#define R(i, j, k) for(int i = (j); i >= (k); --i)
#define ll long long
#define vi vector <int>
#define sz(a) ((int) (a).size())
#define me(f, x) memset(f, x, sizeof(f))
#define uint unsigned int
#define ull unsigned long long 
#define i128 __int128
#define pb emplace_back
using namespace std; 
const int N = 1007;
int n;

int ord[N];
mt19937_64 orz;
map < vi, int > mp;
inline int query(vi S) {
//	for(auto&x : S)
//		x = ord[x]; 
	sort(S.begin(), S.end());
	return Query(S);
} 
void report(int x, int y){
	if(x == -1) return Report(x, y), void();
	Report(x, y);
//	Report(ord[x], ord[y]);
}

int GG;
int val[N];
int vis[N];
int fa[N]; 

inline int get0(vi S){
	for(auto&u : S)if(fa[u] == 0)return u;
	return 0;
}
void slv(vi S) {
	if(sz(S) <= 1) return;
	if(GG) return;
	shuffle(S.begin(), S.end(), orz);
	L(t, 0, sz(S) - 1) {
		int u = S[t], win = 0;
		for(auto&v : S) 
			if(u == v) val[v] = 1;
			else val[v] = query(vi{u, v}), win |= val[v] > 2;
		if(win) {
//			cout << "u = " << u << endl;
			auto dfs = [&] (auto self, vi ls, vi rs) {
				if(!sz(rs)){
					slv(ls);
					return;
				}
				int p = rs[orz() % sz(rs)];
				int fp = 0; 
				for(auto&r : ls) vis[r] = 0;
				for(auto&r : ls)if(r != u) {
					if(query(vi{p, r}) == 2) vis[r] = 1;
				}
				for(auto&r : ls)if(vis[r]) {
					if(query(vi{u, p, r}) == 3) {
						fp = r;
						break; 
					}
				}
//				cout << u << ", " << p << " and " << fp << endl;
				assert(fp != 0);
				vi L_l, L_r;
				vi R_l, R_r;
				vi midS;
				for(auto&r : ls)if(r != fp){
					if(vis[r]) R_l.emplace_back(r);
					else L_l.emplace_back(r);
				}
				midS.emplace_back(p);
				for(auto&r : rs) if(p != r) {
					if(query(vi{r, fp}) == 3) {
						R_r.emplace_back(r);
					} else if(query(vi{r, u, fp}) == 3) {
						midS.emplace_back(r);
					} else {
						L_r.emplace_back(r);
					}
				}
				slv(midS);
				self(self, L_l, L_r);
				self(self, R_l, R_r);
//				cout << "ok solved" << endl;
				
				fa[get0(midS)] = fp;
				if(sz(L_l))fa[get0(L_l)] = fp;
				int xs = 0;
				for(auto&p : R_l) xs ^= p ^ fa[p];
				if(xs)fa[fp] = xs;
				return;
			};
			vi ls, rs;
			for(auto&u : S) 
				if(val[u] <= 2) ls.emplace_back(u);
				else rs.emplace_back(u);
//			cout << "ls : "; for(auto&x : ls) cout << x << ' '; cout << '\n';
//			cout << "rs : "; for(auto&x : rs) cout << x << ' '; cout << '\n';
			dfs(dfs, ls, rs);
			return;
		}
		if(t == 2) {
//			cout<<"GG.., S = ";
//			for(auto&u:S)cout<<u<<' ';
//			cout<<endl;
			return GG = 1, report(-1, -1), void();	
		} 
	} 
//	cout<<"GG??, S = ";
//	for(auto&u:S)cout<<u<<' ';
//	cout<<endl;
	GG = 1, report(-1, -1);
}

void Solve(int N) {
	n = N; 
	if(n == 2)return report(-1, -1), void();
	
	vi S;
	L(i, 1, n) S.emplace_back(i);
	
	slv(S);
	L(i, 1, n) if(fa[i])report(fa[i], i);
}
/*
7 250000
2 3
4 5
6 7
0 0
0 0
0 0
0 0
1
*/