#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); i++)
typedef long long ll;
#define pb push_back
#define st first
#define nd second
void bridge(int a, int b) {
Bridge(min(a, b), max(a, b));
}
void posortuj(vector<int> sciezka, int korzen, int last) {
int sz = sciezka.size();
// rep(i, sz) {
// cout << sciezka[i] << " ";
// }
// cout << '\n';
// cout << "korzen ze sciezka = " << korzen << '\n';
// cout << "last = " << last << '\n';
vector<int> ans;
rep(i, sz) {
int v = sciezka[i];
int poc = 0;
int rozm = ans.size();
int kon = rozm;
int odp = rozm;
while (poc < kon) {
int sr = (poc + kon)/2;
int w = ans[sr];
if (Query(korzen, v, w) == v) {
odp = sr;
kon = sr;
}
else {
poc = sr + 1;
}
}
vector<int> ans2;
rep(j, odp) {
ans2.pb(ans[j]);
}
ans2.pb(v);
for (int j = odp; j < rozm; j++) {
ans2.pb(ans[j]);
}
ans = ans2;
}
// rep(i, sz) {
// cout << ans[i] << " ";
// }
// cout << '\n';
if (sz > 0) {
bridge(korzen, ans[0]);
bridge(ans[sz - 1], last);
}
else {
bridge(korzen, last);
}
// cout << "PLS" << '\n';
rep(i, sz - 1) {
bridge(ans[i], ans[i + 1]);
}
// cout << "SKULL" << '\n';
}
void rozw(vector<int> wierzcholki, int korzen) {
int sz = wierzcholki.size();
// rep(i, sz) {
// cout << wierzcholki[i] << " ";
// }
// cout << '\n';
// cout << "korzen = " << korzen << '\n';
if (sz == 0) {
return ;
}
if (sz == 1) {
bridge(wierzcholki[0], korzen);
return;
}
int los = rand() % sz;
int v = wierzcholki[los];
vector<int> pom[2002];
vector<int> sciezka;
rep(i, sz) {
if (i == los) continue;
int w = wierzcholki[i];
int lca = Query(korzen, v, w);
if (lca == w) {
sciezka.pb(w);
}
else {
pom[lca].pb(w);
}
}
posortuj(sciezka, korzen, v);
rep(i, 2002) {
int sz = pom[i].size();
if (sz == 0) {
continue;
}
rozw(pom[i], i);
}
}
void Solve(int N) {
vector<int> v;
int los = rand() % N;
rep(i, N) {
if (i == los) continue;
v.pb(i);
}
rozw(v, los);
}
