#include "meetings.h"
#include<bits/stdc++.h>
#define st first
#define nd second
#define pb push_back
#define ppb pop_back
#define ii pair<int,int>
#define orta ((bas+son)>>1)
#define sz(x) ((int)x.size())
#define all(x) x.begin(),x.end()
#define inf 1000000000
#define N 300005
using namespace std;
int gsb;
vector<int> u;
vector<multiset<int>> v;
vector<int> sub;
vector<int> f;
struct change {
int a,b,mean;
};
int fcnt(int node,int ata) {
for(auto x:v[node]) {
if(x==ata || f[x]) continue ;
if(sub[x]>gsb/2) return fcnt(x,node);
}
return node;
}
void fsubs(int node,int ata) {
sub[node]=1;
for(auto x:v[node]) {
if(x==ata || f[x]) continue ;
fsubs(x,node);
sub[node]+=sub[x];
}
}
void solve(int node,int nw) {
fsubs(node,0);
gsb=sub[node];
int cnt=fcnt(node,0);
vector<change> q;
f[cnt]=1;
for(auto x:v[cnt]) {
if(f[x]) continue ;
int mid=Query(nw,cnt,x);
if(mid==cnt) continue ;
if(mid==x) {
solve(x,nw);
return ;
}
if(mid==nw) {
q.pb({cnt,nw,1});
q.pb({nw,x,1});
q.pb({cnt,x,-1});
break ;
}
q.pb({cnt,mid,1});
q.pb({mid,x,1});
q.pb({nw,mid,1});
q.pb({cnt,x,-1});
break ;
}
if(!sz(q)) q.pb({cnt,nw,1});
for(auto x:q) {
if(x.mean==1) {
v[x.a].insert(x.b);
v[x.b].insert(x.a);
}
else {
v[x.a].erase(v[x.a].find(x.b));
v[x.b].erase(v[x.b].find(x.a));
}
u[x.a]=u[x.b]=1;
}
}
void Solve(int n) {
u=sub=vector<int>(n,0);
v=vector<multiset<int>>(n);
mt19937 rnd(time(NULL));
vector<int> order;
for(int i=0;i<n;i++) {
order.pb(i);
}
shuffle(all(order),rnd);
int cnt=0;
int root;
for(int i=0;i<n;i++,++cnt) {
if(u[order[i]]) continue ;
if(!cnt) u[root=order[i]]=1;
else if(cnt==1) {
v[root].insert(order[i]);
v[order[i]].insert(root);
u[order[i]]=1;
}
else {
f=vector<int>(n,0);
solve(root,order[i]);
}
}
for(int i=0;i<n;i++) {
for(auto x:v[i]) {
if(x>i) Bridge(i,x);
}
}
}
