#include "meetings.h"
#include "bits/stdc++.h"
using i64 = long long;
#ifdef DEBUG
#include "../debug.h"
#else
#define debug(...) void(23)
#endif
namespace {
void send(int u, int v) {
if (u > v) {
std::swap(u, v);
}
debug(u, v);
Bridge(u, v);
}
std::random_device rd;
std::mt19937 rng(rd());
};
void solve_line(int a, int b, std::vector<int> ids) {
std::shuffle(ids.begin(), ids.end(), rng);
debug(0, ids);
int n = int(ids.size());
if (n == 0) {
send(a, b);
return;
}
int x = ids[0];
std::vector<int> rig;
std::vector<int> lef;
for (int i = 1; i < n; ++i) {
int res = Query(a, x, ids[i]);
if (res == x) {
rig.emplace_back(ids[i]);
} else {
lef.emplace_back(ids[i]);
}
}
solve_line(a, x, lef);
solve_line(x, b, rig);
}
void solve(std::vector<int> ids) {
std::shuffle(ids.begin(), ids.end(), rng);
debug(1, ids);
int n = int(ids.size());
if (n <= 1) {
return;
} else if (n == 2) {
send(ids[0], ids[1]);
return;
}
auto get = [&](int x) -> int {
return int(std::find(ids.begin(), ids.end(), x) - ids.begin());
};
std::vector<int> mid;
std::vector<std::vector<int>> sub(n);
sub[get(ids[0])].emplace_back(ids[0]);
sub[get(ids[1])].emplace_back(ids[1]);
for (int i = 2; i < n; ++i) {
int x = Query(ids[0], ids[1], ids[i]);
if (x != ids[0] && x != ids[1]) {
mid.emplace_back(x);
}
sub[get(x)].emplace_back(ids[i]);
}
std::sort(mid.begin(), mid.end());
mid.erase(std::unique(mid.begin(), mid.end()), mid.end());
for (int i = 0; i < n; ++i) {
solve(sub[i]);
}
solve_line(ids[0], ids[1], mid);
}
void Solve(int N) {
std::vector<int> ids(N);
std::iota(ids.begin(), ids.end(), 0);
solve(ids);
}
