#include "meetings.h"
#include <bits/stdc++.h>
#define Loop(x,l,r) for (ll x = (l); x < (ll)(r); ++x)
#define LoopR(x,l,r) for (ll x = (r)-1; x >= (ll)(l); --x)
typedef long long ll;
typedef std::pair<int, int> pii;
typedef std::pair<ll , ll > pll;
using namespace std;
int query(int i, int j, int k) {
if (i == j || i == k)
return i;
if (j == k)
return j;
return Query(i, j, k);
}
mt19937_64 rd(time(0));
void solve(vector<int> vec)
{
shuffle(vec.begin(), vec.end(), rd);
int rt = query(vec[rd()%vec.size()], vec[rd()%vec.size()], vec[rd()%vec.size()]);
struct dard { vector<int> vec; int rt; };
vector<dard> marg;
for (int v : vec) {
if (v == rt)
continue;
bool found = 0;
Loop (i,0,marg.size()) {
int x = query(rt, marg[i].rt, v);
if (x == rt)
continue;
marg[i].rt = x;
marg[i].vec.push_back(v);
for (int j = i; j > 0; --j) {
if (marg[j-1].vec.size() >= marg[j].vec.size())
break;
swap(marg[j-1].vec, marg[j].vec);
swap(marg[j-1].rt, marg[j].rt);
}
found = 1;
break;
}
if (!found)
marg.push_back({{v}, v});
}
Loop (i,0,marg.size())
Bridge(min(rt, marg[i].rt), max(rt, marg[i].rt));
Loop (i,0,marg.size())
solve(marg[i].vec);
}
void Solve(int N) {
vector<int> a(N);
iota(a.begin(), a.end(), 0);
solve(a);
}
