#include "meetings.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fr first
#define sc second
#define szof(s) (int)s.size()
#define all(s) s.begin(), s.end()
#define mk make_pair
using namespace std;
const int MAXN = 2003; // дерево индексация с 0...n-1
vector <pair<int, int>> ans; // u < v
int n;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int get_rand() {
int x = rng();
if (x < 0) {
x = -x;
}
return x;
};
int gen(int l, int r) {
return l + get_rand() % (r - l + 1);
}
void print(int u, int v) {
if (u > v) {
swap(u, v);
}
Bridge(u, v);
}
void calc(vector<int> &graph) {
int root = -1, son = -1;
while (root == son) {
root = graph[gen(0, szof(graph) - 1)];
son = graph[gen(0, szof(graph) - 1)];
}
// a = root
// b = child
set <int> st;
vector <int> bambook;
map <int, vector<int>> sub;
for (int vertex : graph) {
if (vertex == root || vertex == son) {
continue;
}
int lca = Query(root, son, vertex);
st.insert(lca);
sub[lca].push_back(vertex);
}
st.erase(son);
st.erase(root);
for (int el : st) {
bambook.push_back(el);
}
sort(all(bambook), [&](int A, int B) {
int lca = Query(root, A, B);
return (A == lca);
});
bambook.insert(bambook.begin(), root);
bambook.push_back(son);
for (int i = 0; i + 1 < szof(bambook); i++) {
print(bambook[i], bambook[i + 1]);
}
sub[root].push_back(root);
sub[son].push_back(son);
for (auto el : sub) {
if (szof(el.second) > 1) {
calc(el.second);
}
}
}
void Solve(int nn) {
n = nn;
vector<int> graph;
for (int i = 0; i < n; i++) {
graph.push_back(i);
}
calc(graph);
}
/*
5
0 1
1 2
2 3
3 4
*/
