#include "meetings.h"
#include <bits/stdc++.h>
#include <chrono>
#include <random>
using namespace std;
using namespace chrono;
mt19937 rng(chrono::steady_clock().now().time_since_epoch().count());
const int N = 2e3 + 67;
#define all(X) X.begin(), X.end()
#ifndef ONLINE_JUDGE
#define dbg(x) \
cerr << #x << " "; \
print(x); \
cerr << endl;
#else
#define dbg(x)
#endif
void print(long long t) { cerr << t; }
void print(int t) { cerr << t; }
void print(string t) { cerr << t; }
void print(char t) { cerr << t; }
void print(double t) { cerr << t; }
void print(long double t) { cerr << t; }
void print(unsigned long long t) { cerr << t; }
template <class T, class V>
void print(pair<T, V> p);
template <class T>
void print(vector<T> v);
template <class T>
void print(set<T> v);
template <class T, class V>
void print(map<T, V> v);
template <class T>
void print(multiset<T> v);
template <class T, class V>
void print(T v[], V n)
{
cerr << "[";
for (int i = 0; i < n; i++)
{
cerr << v[i] << " ";
}
cerr << "]";
}
template <class T, class V>
void print(pair<T, V> p)
{
cerr << "{";
print(p.first);
cerr << ",";
print(p.second);
cerr << "}";
}
template <class T>
void print(vector<T> v)
{
cerr << "[ ";
for (T i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
template <class T>
void print(set<T> v)
{
cerr << "[ ";
for (T i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
template <class T>
void print(multiset<T> v)
{
cerr << "[ ";
for (T i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
template <class T, class V>
void print(map<T, V> v)
{
cerr << "[ ";
for (auto i : v)
{
print(i);
cerr << " ";
}
cerr << "]";
}
void answer(int u, int v)
{
dbg(u);
dbg(v);
if (u == v)
return;
if (u > v)
swap(u, v);
Bridge(u - 1, v - 1);
}
int query(int v, int u, int w)
{
return Query(v - 1, u - 1, w - 1) + 1;
}
int nd;
bool cmp(int u, int v)
{
if(u == v)
return false;
return query(nd, u, v) == u;
}
void slv(int node, vector<int> vec)
{
vector<int> sub[N];
int n = vec.size();
dbg(n);
dbg(vec);
dbg(node);
if (n == 0)
{
return;
}
if(n == 1)
{
answer(node, vec[0]);
return;
}
int v = rng() % n;
v = vec[v];
dbg(v);
vector<int> path;
for (auto x : vec)
{
if(x == v)
continue;
int h = query(node, v, x);
if (h == x)
path.push_back(x);
else
sub[h].push_back(x);
}
nd = node;
sort(all(path), cmp);
path.push_back(v);
dbg(path);
answer(node, path[0]);
for (int i = 1; i < (int)path.size(); i++)
{
answer(path[i - 1], path[i]);
}
for (auto i : path)
{
dbg(i);
dbg(sub[i]);
slv(i, sub[i]);
}
dbg(sub[node]);
slv(node, sub[node]);
}
void Solve(int NN)
{
vector<int> vec;
for (int i = 2; i <= NN; i++)
vec.push_back(i);
slv(1, vec);
}
