#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 2000;
mt19937 rng(time(0));
int ucmp;
void write(int u, int v) {
u--, v--;
Bridge(min(u, v), max(u, v));
}
int get(int u, int v, int w) {
return Query(u - 1, v - 1, w - 1) + 1;
}
void solveSmall(vector<int> vec) {
if (vec.size() == 1)
return;
if (vec.size() == 2) {
write(vec[0], vec[1]);
return;
}
int x = get(vec[0], vec[1], vec[2]);
for (auto y: vec)
if (x != y)
write(x, y);
}
bool cmp(int x, int y) {
return get(ucmp, x, y) == x;
}
void checkPath(vector<int> path, int u, int v) {
ucmp = u;
sort(path.begin(), path.end(), cmp);
for (int i = 1; i < path.size(); i++)
write(path[i - 1], path[i]);
if (path.size() == 0)
write(u, v);
else {
write(u, path[0]);
write(path.back(), v);
}
}
void solve(vector<int> vec) {
if (vec.size() <= 3) {
solveSmall(vec);
return;
}
shuffle(vec.begin(), vec.end(), rng);
int u = vec[0], v = vec[1];
vector<int> path, x[N + 10];
for (int i = 2; i < vec.size(); i++) {
int w = get(u, v, vec[i]);
x[w].push_back(vec[i]);
if (w == vec[i])
path.push_back(w);
}
checkPath(path, u, v);
x[u].push_back(u);
x[v].push_back(v);
for (auto u: vec)
if (x[u].size())
solve(x[u]);
}
void Solve(int N) {
vector<int> vec;
for (int i = 1; i <= N; i++)
vec.push_back(i);
solve(vec);
}
