// In the name of Allah
#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
typedef long long int ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef complex<ld> cld;
#define all(x) (x).begin(),(x).end()
#define len(x) ((ll) (x).size())
#define F first
#define S second
#define pb push_back
#define sep ' '
#define endl '\n'
#define Mp make_pair
#define kill(x) cout << x << '\n', exit(0)
#define set_dec(x) cout << fixed << setprecision(x);
#define file_io(x,y) freopen(x, "r", stdin); freopen(y, "w", stdout);
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
const int maxn = 2000 + 4;
int n;
vector<int> adj[maxn];
int M[maxn], mark[maxn];
int sz[maxn], h[maxn];
vector<int> ls[maxn], lsx;
void pre_dfs(int v, int p, int d) {
sz[v] = 1; h[v] = d;
for (int u : adj[v]) {
if (mark[u] || u == p) continue;
pre_dfs(u, v, d + 1);
sz[v] += sz[u];
}
}
int get_cent(int v, int p, int SZ) {
for (int u : adj[v]) {
if (mark[u] || u == p) continue;
if (sz[u] * 2 > SZ) return get_cent(u, v, SZ);
}
return v;
}
void dfsx(int v, int p, int R) {
ls[R].pb(v);
for (int u : adj[v]) {
if (mark[u] || u == p) continue;
dfsx(u, v, R);
}
}
bool cmp(int u, int v) {
return (len(ls[u]) > len(ls[v]));
}
void addE(int u, int v) {
adj[u].pb(v); adj[v].pb(u);
M[u] = 1; M[v] = 1;
}
void delE(int u, int v) {
adj[u].erase(find(all(adj[u]), v));
adj[v].erase(find(all(adj[v]), u));
}
void addV(int u1, int u2, int v) {
delE(u1, u2); addE(u1, v); addE(v, u2);
}
int fixV(int rt, int v, int u, int x) {
mark[v] = 1;
for (int w : lsx) {
if (w == u) continue;
for (int f : ls[w]) mark[f] = 1;
}
if (h[u] > h[v]) return u;
else return rt;
}
void addx(int rt, int x) {
pre_dfs(rt, -1, 0);
int v = get_cent(rt, -1, sz[rt]);
lsx.clear(); ls[v].clear();
for (int u : adj[v]) {
if (mark[u]) continue;
ls[u].clear(); dfsx(u, v, u);
lsx.pb(u);
}
sort(all(lsx), cmp);
if (len(lsx) % 2 == 1) lsx.pb(v);
for (int i = 0; i < len(lsx); i += 2) {
int u1 = lsx[i], u2 = lsx[i + 1];
int R = Query(u1, u2, x);
if (R == v) continue;
if (R == x) {
if (u2 == v || Query(v, u1, x) == x) addV(v, u1, x);
else addV(v, u2, x);
}
else if (R == u1) addx(fixV(rt, v, u1, x), x);
else if (R == u2) addx(fixV(rt, v, u2, x), x);
else {
if (u2 == v || Query(v, u1, x) == R) {
addV(v, u1, R); addE(R, x);
}
else {
addV(v, u2, R); addE(R, x);
}
}
return ;
}
addE(v, x);
return ;
}
void Solve(int N) {
n = N;
int vx = 0; M[vx] = 1;
for (int v = 0; v < n; v++) {
if (M[v]) continue;
for (int i = 0; i < n; i++) mark[i] = (1 - M[i]);
addx(vx, v);
}
for (int u = 0; u < n; u++) {
for (int v : adj[u]) {
if (v <= u) continue;
Bridge(u, v);
}
}
}
