#include<bits/stdc++.h>
#include"meetings.h"
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 2e3 + 5;

int ask(int u,int v,int w)
{
	return Query(u-1, v-1, w-1) + 1;
}
void answer(int u,int v)
{
	if(u > v) swap(u, v);
	Bridge(u-1, v-1);
}

vector<int> g[MAXN];

void add_edge(int u,int v)
{
	g[u].emplace_back(v);
	g[v].emplace_back(u);
}
void del_edge(int u,int v)
{
	g[u].erase(find(g[u].begin(), g[u].end(), v));
	g[v].erase(find(g[v].begin(), g[v].end(), u));
}

bool del[MAXN];
int siz[MAXN], mxson[MAXN];
void dfs_siz(int u,int fa)
{
	siz[u] = 1; mxson[u] = 0;
	for(int v: g[u]) if(v != fa && !del[v])
	{
		dfs_siz(v,u);
		siz[u] += siz[v];
		mxson[u] = max(mxson[u], siz[v]);
	}
}

int rt, totsiz;
void dfs_rt(int u,int fa)
{
	mxson[u] = max(mxson[u], totsiz - siz[u]);
	if(mxson[u] < mxson[rt]) rt = u;
	for(int v: g[u]) if(v != fa && !del[v])
		dfs_rt(v,u);
}

void divid(int u,int k)
{
	dfs_siz(u,0);
	rt = u; totsiz = siz[u];
	dfs_rt(u,0);
	u = rt; del[u] = 1;
	
	vector<int> ch;
	for(int v: g[u]) if(!del[v])
		ch.emplace_back(v);
	sort(ch.begin(), ch.end(), [&] (int x,int y){
		return siz[x] > siz[y];
	});
	
	for(int v: ch)
	{
		int w = ask(u, v, k);
		if(w == u) continue;
		if(w == v)
		{
			divid(v, k);
			return;
		}
		
		del_edge(u,v);
		add_edge(u, w);
		add_edge(v, w);
		if(w != k) add_edge(w, k);
		return;
	}
	
	add_edge(u, k);
}

void Solve(int n)
{
	mt19937 gen(114514);
	vector<int> id(n);
	iota(id.begin(), id.end(), 1);
	shuffle(id.begin(), id.end(), gen);
	
	for(int u: id) if(u != id[1])
	{
		divid(id[1], u);
	}
	
	for(int u=1; u<=n; ++u)
		for(int v: g[u]) if(u < v)
			answer(u, v);
}