#include<bits/stdc++.h>
#include"meetings.h"
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef vector<int> vi;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
typedef vector<vii> vvii;
#define INF INT_MAX
#define MOD 1000000007
#define all(x) x.begin(), x.end()
// holds nearest known children branch root
vvi B;
map<ii, int> csr;
int ask(int u, int v){
if(u > v) swap(u, v);
if(csr.find({u, v}) == csr.end()){
int k = Query(0, u, v);
csr[{u, v}] = k;
}
return csr[{u, v}];
}
int doshit(int rt, int u){
if(rt == u) return -7;
bool set = false;
for(auto &v : B[rt]){
int par = ask(u, v);
if(par == rt) continue;
set = true;
if(par == v){
doshit(v, u);
}else if(par == u){
doshit(u, v);
v = u;
}else{
doshit(par, u);
doshit(par, v);
v = par;
}
break;
}
if(!set) {B[rt].push_back(u); random_shuffle(all(B[rt]));}
return 0;
}
void Solve(int N){
srand(123456);
B.resize(N+10);
vi rem;
for(int x = 1; x < N; x++)
rem.push_back(x);
random_shuffle(all(rem));
while(rem.size() >= 2){
int u = rem.back(); rem.pop_back();
int v = rem.back(); rem.pop_back();
int par = ask(u, v);
if(doshit(par, u) == -7) rem.push_back(u);
if(doshit(par, v) == -7) rem.push_back(v);
cout << "For nodes: " << u << ", " << v << endl;
for(int u = 0; u < N; u++){
cout << u << " ::: ";
for(auto v : B[u]) cout << v << " ";
cout << endl;
}
cout << "-----" << endl;
}
if(rem.size() == 1){
int u = rem.back(); rem.pop_back();
for(int x = 1; x < N; x++)
if(x != u) rem.push_back(x);
random_shuffle(all(rem));
set<int> vviiss;
bool done = false;
while(rem.size()){
int v = rem.back(); rem.pop_back();
if(vviiss.find(v) != vviiss.end()) continue;
int par = ask(u, v);
if(doshit(par, u) == -7){
queue<int> dpd; dpd.push(v);
vviiss.insert(v);
while(!dpd.empty()){
int z = dpd.front(); dpd.pop();
for(auto j : B[z]){
vviiss.insert(j);
dpd.push(j);
}
}
}else{
done = true;
cout << "For nodes: " << u << ", " << v << endl;
for(int u = 0; u < N; u++){
cout << u << " ::: ";
for(auto v : B[u]) cout << v << " ";
cout << endl;
}
cout << "-----" << endl;
break;
}
}
if(!done){
if(B[0].empty()) B[0].push_back(u);
else{
int v = B[0][0];
B[0][0] = u;
B[u].push_back(v);
}
}
}
for(int u = 0; u < N; u++)
for(auto v : B[u])
Bridge(u, v);
return;
}
