#include "meetings.h"
#include "bits/stdc++.h"
using namespace std;
#ifdef duc_debug
#include "bits/debug.h"
#else
#define debug(...)
#endif
const int maxn = 2005;
vector<int> g[maxn];
int cur_anc[maxn];
int n;
bool mark[maxn], in[maxn];
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
void calc(int root, int prev, vector<int> &cand) {
for (int i = 0; i < (int)cand.size(); ++i) {
if (cand[i] == root) {
cand.erase(cand.begin() + i);
break;
}
}
// debug(root, cand);
if (cand.empty()) return;
while (!cand.empty()) {
for (auto i:cand) {
mark[i] = 0;
in[i] = 1;
}
shuffle(cand.begin(), cand.end(), rng);
vector<int> nxt;
int x = cand[0];
nxt.push_back(x);
mark[x] = 1;
for (int i = 1; i < (int)cand.size(); ++i) {
if (cur_anc[cand[i]] and in[cur_anc[cand[i]]]) {
// debug(root, cand[i], cur_anc[cand[i]]);
mark[cand[i]] = 1;
nxt.push_back(cand[i]);
continue;
}
int p = Query(root, x, cand[i]);
if (p == root) {
continue;
}
nxt.push_back(cand[i]);
mark[cand[i]] = 1;
if (p == cand[i]) {
cur_anc[x] = cand[i];
x = cand[i];
} else {
cur_anc[cand[i]] = x;
}
}
// debug(root, x);
Bridge(min(root, x), max(root, x));
vector<int> new_cand;
for (auto i:cand) {
in[i] = 0;
if (!mark[i]) {
new_cand.push_back(i);
}
}
cand.swap(new_cand);
calc(x, root, nxt);
}
}
void Solve(int N) {
n = N;
vector<int> cand;
for (int i = 0; i < n; ++i) {
cand.push_back(i);
}
calc(0, -1, cand);
}
