#include <bits/stdc++.h>
#include "meetings.h"
#define ff first
#define ss second
using namespace std;
typedef pair<int, int> pii;
const int maxn = 2010;
int n;
int sz[maxn];
bool mark[maxn];
vector<int> grafo[maxn];
void dfs(int u, int p)
{
sz[u] = 1;
for (auto v: grafo[u])
{
if (v == p || mark[v]) continue;
dfs(v, u);
sz[u] += sz[v];
}
}
int centroid(int u, int p, int S)
{
for (auto v: grafo[u])
if (v != p && !mark[v] && sz[v] > S/2)
return centroid(v, u, S);
return u;
}
void add_edge(int a, int b)
{
grafo[a].push_back(b);
grafo[b].push_back(a);
}
void rem_edge(int a, int b)
{
for (int i = 0; i < grafo[a].size(); i++)
{
int v = grafo[a][i];
if (v == b)
{
swap(grafo[a][i], grafo[a].back());
grafo[a].pop_back();
break;
}
}
for (int i = 0; i < grafo[b].size(); i++)
{
int v = grafo[b][i];
if (v == a)
{
swap(grafo[b][i], grafo[b].back());
grafo[b].pop_back();
break;
}
}
}
void Solve(int N)
{
n = N;
add_edge(1, 2);
for (int i = 3; i <= n; i++)
{
memset(mark, 0, sizeof mark);
int at = 1;
bool ok = 0;
vector<pii> toadd, torem;
while (true)
{
dfs(at, 0);
int c = centroid(at, 0, sz[at]);
mark[c] = 1;
int go = 0;
for (auto v: grafo[c])
{
if (mark[v]) continue;
int k = Query(c-1, v-1, i-1)+1;
if (k == c) continue;
go = v;
if (k == i)
{
torem.push_back({c, v});
toadd.push_back({c, i}); toadd.push_back({v, i});
ok = 1;
break;
}
}
if (!go)
{
if (!ok) add_edge(c, i);
break;
}
at = go;
}
for (auto pp: torem)
rem_edge(pp.ff, pp.ss);
for (auto pp: toadd)
add_edge(pp.ff, pp.ss);
}
set<pair<int, int>> st;
for (int i = 1; i <= n; i++)
for (auto j: grafo[i])
st.insert({min(i, j), max(i, j)});
for (auto pp: st)
Bridge(pp.ff-1, pp.ss-1);
}
