#include "meetings.h"
#include "bits/stdc++.h"
#include <unordered_set>
#include <unordered_map>
#include <random>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
constexpr ll MOD = 1'000'000'007LL; /*998'244'353LL;*/
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(n); (i)++)
template<class T> bool chmax(T &a, const T &b){ if(a<b){ a=b; return 1; } return 0; }
template<class T> bool chmin(T &a, const T &b){ if(b<a){ a=b; return 1; } return 0; }
constexpr int dy[4]={ -1,0,1,0 };
constexpr int dx[4]={ 0,-1,0,1 };
namespace{
map<pair<pair<int,int>,int>,int> memo;
int query(int u, int v, int w){
if(u > v) swap(u, v);
if(v > w) swap(v, w);
if(u > v) swap(u, v);
if(u == v) return v;
if(v == w) return v;
if(memo.count({{u,v},w})) return memo[{{u,v},w}];
return memo[{{u,v},w}] = Query(u, v, w);
}
vector<int> e[2000];
bool used[2000];
int sz;
int CentroidDecomposition(int n, int p){ // find one centroid
int ma = 0;
int sum = 1;
rep(i, e[n].size()){
if(e[n][i] == p || used[e[n][i]]) continue;
int ret = CentroidDecomposition(e[n][i], n);
if(ret <= 0) return ret;
chmax(ma, ret);
sum += ret;
}
if(ma <= sz / 2 && sz - sum <= sz / 2) return -n;
return sum;
}
int size(int n, int p){
int sum = 1;
rep(i, e[n].size()){
if(e[n][i] == p || used[e[n][i]]) continue;
sum += size(e[n][i], n);
}
return sum;
}
void fill(int n, int p){
used[n] = true;
sz--;
rep(i, e[n].size()){
if(e[n][i] == p || used[e[n][i]]) continue;
fill(e[n][i], n);
}
}
void erase(vector<int> &v, int x){
rep(i, v.size()){
if(v[i] == x){
v.erase(v.begin()+i);
break;
}
}
}
};
void Solve(int N) {
vector<int> v;
rep(i, N) v.pb(i);
random_device seed_gen;
mt19937 engine(seed_gen());
shuffle(all(v), engine);
e[v[0]].pb(v[1]);
e[v[1]].pb(v[0]);
for(int i=2; i<N; i++){
sz = i;
memset(used, false, sizeof(used));
bool flg = true;
int root = v[0];
while(flg){
int u = -CentroidDecomposition(root, -1); // O(N^2 log N)
assert(u >= 0);
vector<pair<int,int>> tmp;
rep(j, e[u].size()){
if(used[e[u][j]]) continue;
tmp.pb({size(e[u][j], u), e[u][j]});
}
sort(all(tmp));
reverse(all(tmp));
if(tmp.size() == 0){
e[u].pb(v[i]);
e[v[i]].pb(u);
break;
}
bool ok = false;
for(int j=0; j<tmp.size(); j+=2){
if(j+1 == tmp.size()){
if(!ok){
int ret = query(u, tmp[j].second, v[i]);
if(ret == v[i]){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(v[i]);
e[tmp[j].second].pb(v[i]);
e[v[i]].pb(u);
e[v[i]].pb(tmp[j].second);
ok = true;
flg = false;
break;
}
if(ret == tmp[j].second){
ok = true;
root = tmp[j].second;
continue;
}
if(ret != u){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(ret);
e[tmp[j].second].pb(ret);
e[ret].pb(u);
e[ret].pb(tmp[j].second);
ok = true;
flg = false;
for(int k=i+1; k<v.size(); k++){
if(v[k] == ret) swap(v[k], v[i]);
}
break;
}
}
fill(tmp[j].second, u);
}
else{
if(!ok){
int ret = query(tmp[j].second, tmp[j+1].second, v[i]);
if(ret == v[i]){
int ret2 = query(u, tmp[j].second, v[i]);
if(ret2 == v[i]){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(v[i]);
e[tmp[j].second].pb(v[i]);
e[v[i]].pb(u);
e[v[i]].pb(tmp[j].second);
}
else{
erase(e[u], tmp[j+1].second);
erase(e[tmp[j+1].second], u);
e[u].pb(v[i]);
e[tmp[j+1].second].pb(v[i]);
e[v[i]].pb(u);
e[v[i]].pb(tmp[j+1].second);
}
ok = true;
flg = false;
break;
}
if(ret == tmp[j].second){
ok = true;
root = tmp[j].second;
fill(tmp[j+1].second, u);
continue;
}
if(ret == tmp[j+1].second){
ok = true;
root = tmp[j+1].second;
fill(tmp[j].second, u);
continue;
}
if(ret != u){
int ret2 = query(u, tmp[j].second, ret);
if(ret2 == ret){
erase(e[u], tmp[j].second);
erase(e[tmp[j].second], u);
e[u].pb(ret);
e[tmp[j].second].pb(ret);
e[ret].pb(u);
e[ret].pb(tmp[j].second);
}
else{
erase(e[u], tmp[j+1].second);
erase(e[tmp[j+1].second], u);
e[u].pb(ret);
e[tmp[j+1].second].pb(ret);
e[ret].pb(u);
e[ret].pb(tmp[j+1].second);
}
for(int k=i+1; k<v.size(); k++){
if(v[k] == ret) swap(v[k], v[i]);
}
ok = true;
flg = false;
break;
}
fill(tmp[j].second, u);
fill(tmp[j+1].second, u);
}
else{
fill(tmp[j].second, u);
fill(tmp[j+1].second, u);
}
}
}
if(!ok){
e[u].pb(v[i]);
e[v[i]].pb(u);
break;
}
used[u] = true;
sz--;
}
/*rep(j, N){
cout << j << ":";
rep(k, e[j].size()){
cout << " " << e[j][k];
}
cout << endl;
}*/
}
vector<pair<int,int>> ans;
rep(i, N){
rep(j, e[i].size()){
ans.pb({min(i, e[i][j]), max(i, e[i][j])});
}
}
sort(all(ans));
ans.erase(unique(all(ans)), ans.end());
rep(i, N-1){
Bridge(ans[i].first, ans[i].second);
}
}
