#include <bits/stdc++.h>
#include "meetings.h"
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int p[2009];
vector<int> sub[2009];
int done[2009];
vector<int> cur;
int prt[2009];
void dfs(int v){
done[v] = 1;
for(auto u : sub[v])
if(done[u] == 0)
dfs(u);
cur.pb(v);
}
void calc(vector<int> all){
if(all.size() <= 1) return;
vector<vector<int>> groups;
int root = all.back();
done[root] = 1;
for(auto u : all){
if(done[u]) continue;
for(auto &v : groups){
int tmp = Query(root, v.back(), u);
if(tmp == root)
continue;
if(u != tmp)
sub[tmp].pb(u);
if(v.back() != tmp)
sub[tmp].pb(v.back());
cur.clear();
dfs(tmp);
v.insert(v.end(), cur.begin(), cur.end());
break;
}
if(done[u] == 0){
cur.clear();
dfs(u);
groups.pb(cur);
}
}
for(auto u : all) done[u] = 0;
for(auto v : groups){
p[v.back()] = root;
calc(v);
}
}
void Solve(int n){
vector<int> all;
for(int i = n-1; i >= 0; --i)
all.pb(i);
calc(all);
for(int i = 1; i < n; ++i){
//cout << i << ' ' << p[i] << '\n';
Bridge(min(i, p[i]), max(i, p[i]));
}
}
