#include "meetings.h"
#include <bits/stdc++.h>
using namespace std;
#define mp make_pair
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
vector<int> sz;
vector<bool> ban, done;
vector<vector<int> > graph;
void add(int a, int b){
graph[a].pb(b);
graph[b].pb(a);
}
void del(int a, int b){
graph[a].erase(find(graph[a].begin(), graph[a].end(), b));
graph[b].erase(find(graph[b].begin(), graph[b].end(), a));
}
void dfs(int node, int p){
sz[node]=1;
for (auto num:graph[node])if (num!=p&&!ban[num])dfs(num, node), sz[node]+=sz[num];
}
int find_centroid(int node, int p, int size){
for (auto num:graph[node])if (num!=p&&!ban[num]&&sz[num]>size/2)return find_centroid(num, node, size);
return node;
}
void insert(int node, int v){
dfs(node, -1);
if (sz[node]==1){
add(node, v);
return;
}
if (sz[node]==2){
int a;
for (auto num:graph[node])if (!ban[num])a=num;
int res=Query(node, a, v);
if (res==a||res==node){
add(res, v);
done[v]=1;
return;
}
else{
del(node, a);
add(node, res);
add(a, res);
if (res!=v)add(res, v);
done[v]=done[res]=1;
return;
}
}
int c=find_centroid(node, -1, sz[node]);
vector<int> vect;
for (auto num:graph[c])if (!ban[num])vect.pb(num);
for (int i=0; i<vect.size(); i+=2){
if (i==vect.size()-1){
insert(vect[i], v);
return;
}
int res=Query(vect[i], vect[i+1], v);
if (res==vect[i]||res==vect[i+1]){
ban[c]=1;
insert(res, v);
return;
}
else if (res==c)ban[vect[i]]=ban[vect[i+1]]=1;
else{
int a=(Query(vect[i], c, v)==c?vect[i+1]:vect[i]);
del(node, a);
add(node, res);
add(a, res);
if (res!=v)add(res, v);
done[v]=done[res]=1;
return;
}
}
add(node, v);
}
void Solve(int n){
graph.resize(n);
sz.resize(n);
done.resize(n, 0);
done[0]=done[1]=1;
add(0, 1);
for (int i=0; i<n; ++i)if (!done[i])ban.assign(n, 0), insert(0, i);
for (int i=0; i<n; ++i)for (auto num:graph[i])if (num<i)Bridge(num, i);
}
