#include "meetings.h"
#include <bits/stdc++.h>
#define _CRT_SECURE_NO_WARNINGS
using namespace std;
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define uniq(x) x.resize(unique(all(x)) - x.begin());
#define sort_uniq(x) sort(all(x)), uniq(x);
#define ll long long
#define ld long double
#define pii pair<int, int>
#define pll pair<ll, ll>
#define V vector
#define V2dll V<V<ll>>
#define V2dint V<V<int>>
#define V2dchar V<V<char>>
#define V2dbool V<V<bool>>
#define V3dll V<V<V<ll>>>
#define V3dint V<V<V<int>>>
#define V3dchar V<V<V<char>>>
#define lb lower_bound
#define ub upper_bound
#define pb push_back
#define eb emplace_back
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#define INF INT32_MAX
#define blt __builtin_popcount
#define clr(x) x.clear()
#define ff first
#define ss second
#define popf pop_front
#define popb pop_back
#define sz(x) int(x.size())
#define rep(a,b,c,d) for(int a = b;a <= c; a += d)
#define repl(a,b,c,d) for(int a = b; a >= c; a -= d)
mt19937_64 rng(chrono::steady_clock().now().time_since_epoch().count());
const int N = 2005;
V<int> sub[N];
int qr(int u, int v, int w) {
return Query(u - 1, v - 1, w - 1) + 1;
}
void br(int u, int v) {
Bridge(min(u, v) - 1, max(u, v) - 1);
}
void slv(V<int> list) {
int n = sz(list);
if (n == 1)
return;
if (n == 2) {
br(list[0], list[1]);
return;
}
if (n == 3) {
int x = qr(list[0], list[1], list[2]);
rep(i, 0, 2, 1) if (list[i] != x) {
br(x, list[i]);
}
return;
}
int root = rng() % n;
int v = root;
while (v == root) {
v = rng() % n;
}
v = list[v];
root = list[root];
for (auto x : list) {
sub[x].clear();
}
V<int> path;
path.pb(v);
for (auto x : list) {
if (x == root || x == v) {
continue;
}
int h = qr(x, root, v);
if (h == x) {
path.pb(x);
}
sub[h].pb(x);
}
sort(path.begin() + 1, path.end(), [&](int x, int y) {
return (qr(x, y, root) != x);
});
path.pb(root);
sub[v].pb(v);
sub[root].pb(root);
for (auto i : path) {
slv(sub[i]);
}
rep(i, 0, sz(path) - 2, 1) {
br(path[i], path[i + 1]);
}
}
void Solve(int N) {
V<int> cur;
rep(i, 1, N, 1)
cur.pb(i);
slv(cur);
}
