#include <bits/stdc++.h>
#define rep(a,b,c) for(auto a = (b); a != (c); a++)
#define repD(a,b,c) for(auto a = (b); a != (c); a--)
#define repIn(a, b) for(auto a : (b))
#define repIn2(a, b, c) for(auto [a, b] : (c))
constexpr bool dbg = 0;
#define DEBUG if constexpr(dbg)
#define DC DEBUG std::cerr
#define eol std::endl
#define ll long long
#define pb push_back
using namespace std;
#include "meetings.h"
mt19937 rnd(2137);
void myBridge(int v, int u) {
DC << " @@@ Bridge " << v << ' ' << u << eol;
if(u > v) swap(u, v);
Bridge(u, v);
}
void sortPath(int S, int E, vector<int> V) {
DC << " Sorting path: " << S << " ( ";
repIn(i, V) DC << i << ' ';
DC << ") " << E << eol;
if(V.empty()) {
myBridge(S, E);
return;
}
auto mid = V[rnd() % V.size()];
vector<int> L, R;
repIn(i, V) if(i != mid) (Query(S, i, mid) == i ? L : R).pb(i);
sortPath(S, mid, L);
sortPath(mid, E, R);
}
void DQ(vector<int> V) {
DC << "DQ: ";
repIn(i, V) DC << i << ' ';
DC << eol;
if(V.size() == 2) myBridge(V[0], V[1]);
if(V.size() <= 2) return;
int S = rnd() % V.size(), E = rnd() % (V.size() - 1);
if(E >= S) E++;
S = V[S], E = V[E];
unordered_map<int, vector<int>> subtree;
vector<int> path;
subtree[S].pb(S);
subtree[E].pb(E);
repIn(i, V) if(i != S && i != E) {
auto qa = Query(S, E, i);
if(qa == i) path.pb(i);
subtree[qa].pb(i);
}
sortPath(S, E, path);
repIn2(pathGuy, st, subtree) DQ(st);
}
void Solve(int N) {
vector<int> V;
rep(i, 0, N) V.pb(i);
DQ(V);
}
