#include "meetings.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
using namespace std;
const int MAXN = 2003; // дерево индексация с 0...n-1
vector <pair<int, int>> ans; // u < v
int n;
struct DSU {
vector <int> pr;
vector <int> sz;
DSU (int n) {
pr.resize(n);
sz.resize(n);
for (int i = 0; i < n; i++) {
pr[i] = i;
sz[i] = 1;
}
}
int findp(int v) {
if (v == pr[v]) {
return v;
}
return pr[v] = findp(pr[v]);
}
void unite(int a, int b) {
a = findp(a);
b = findp(b);
if (a == b) {
return;
}
if (sz[a] > sz[b]) {
swap(a, b);
}
pr[a] = b;
sz[b] += sz[a];
}
};
void build(int v, vector <bool> used) {
vector <int> sub(n, 0);
vector <pair<int, int>> sub_root(n, make_pair(-1e9, -1));
DSU dsu(n);
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
if (used[i] && used[j]) {
if (i != v && j != v) {
int x = Query(i, j, v);
if (x == i || x == j) {
if (x == i) {
sub[i]++;
}
else if (x == j) {
sub[j]++;
}
dsu.unite(i, j);
}
}
}
}
}
set <int> subtrees;
for (int i = 0; i < n; i++) {
if (used[i] && i != v) {
int boss = dsu.findp(i);
subtrees.insert(boss);
if (sub_root[boss].first < sub[i]) {
sub_root[boss].first = sub[i];
sub_root[boss].second = i;
}
}
}
for (int el : subtrees) {
ans.push_back(make_pair(v, sub_root[el].second));
vector <int> vec;
for (int i = 0; i < n; i++) {
if (dsu.findp(i) == el) {
used[i] = 1;
vec.push_back(i);
} else {
used[i] = 0;
}
}
int x = rand() % vec.size();
build(vec[x], used);
}
}
void Solve(int nn) {
n = nn;
vector <bool> used(n, true);
build(0, used);
for (auto &el : ans) {
if (el.first > el.second) {
swap(el.first, el.second);
}
Bridge(el.first, el.second);
}
}
