#include <bits/stdc++.h>
#include "meetings.h"
using namespace std;
set<int> s[200001];
int sz[200001],d[200001];
int n;
void dfs(int i,int p)
{
//cout<<i<<" ";
sz[i]=1;
for(auto it=s[i].begin(); it!=s[i].end(); it++)
{
int nb=*it;
if(nb==p||d[nb])continue;
dfs(nb,i);
sz[i]+=sz[nb];
}
}
int all;
int cent(int i,int p)
{
for(auto it=s[i].begin(); it!=s[i].end(); it++)
{
int nb=*it;
if(nb==p||d[nb])continue;
if(sz[nb]>all/2)return cent(nb,i);
}
return i;
}
set<int> ver;
int curr;
void hey(int x)
{
//cout<<x<<" innnn "<<endl;
dfs(x,-1);
//cout<<endl;
all=sz[x];
if(all==1)
{
s[x].insert(curr);
s[curr].insert(x);
return;
}
int c=cent(x,-1);
//cout<<c<<endl;
d[c]=1;
vector<int> nb;
for(auto it=s[c].begin(); it!=s[c].end(); it++)
if(!d[*it])nb.push_back(*it);
for(int i=1; i<nb.size(); i+=2)
{
int nb1=nb[i-1];
int nb2=nb[i];
int y=Query(nb1,nb2,curr);
if(y==nb1)
{
hey(nb1);
return;
}
if(y==nb2)
{
hey(nb2);
return;
}
if(y==curr)
{
int yy=Query(nb1,c,curr);
if(yy==curr)
{
s[nb1].erase(c);
s[c].erase(nb1);
s[curr].insert(nb1);
s[nb1].insert(curr);
s[curr].insert(c);
s[c].insert(curr);
return;
}
else
{
s[nb2].erase(c);
s[c].erase(nb2);
s[curr].insert(nb2);
s[nb2].insert(curr);
s[curr].insert(c);
s[c].insert(curr);
return;
}
}
if(y!=c)
{
int yy=Query(nb1,c,curr);
s[curr].insert(y);
s[y].insert(curr);
ver.erase(y);
if(yy==y)
{
s[nb1].erase(c);
s[c].erase(nb1);
s[y].insert(nb1);
s[nb1].insert(y);
s[y].insert(c);
s[c].insert(y);
return;
}
else
{
s[nb2].erase(c);
s[c].erase(nb2);
s[y].insert(nb2);
s[nb2].insert(y);
s[y].insert(c);
s[c].insert(y);
return;
}
}
}
if(nb.size()%2==1)
{
int nb1=nb[nb.size()-1];
int y=Query(nb1,c,curr);
//cout<<"here "<<y<<" "<<nb1<<endl;
if(y==c)
{
s[c].insert(curr);
s[curr].insert(c);
return;
}
if(y==nb1)
{
hey(nb1);
return;
}
if(curr!=y)
{
s[curr].insert(y);
s[y].insert(curr);
ver.erase(y);
}
s[nb1].erase(c);
s[c].erase(nb1);
s[y].insert(nb1);
s[nb1].insert(y);
s[y].insert(c);
s[c].insert(y);
}
else
{
s[c].insert(curr);
s[curr].insert(c);
}
}
void Solve(int N)
{
n=N;
for(int i=1; i<n; i++)
ver.insert(i);
while(ver.size())
{
for(int i=0; i<n; i++)
d[i]=0;
curr=*ver.begin();
ver.erase(curr);
hey(0);
/*for(int i=0; i<n; i++)
{
for(auto it=s[i].begin(); it!=s[i].end(); it++)
{
int nb=*it;
cout<<i<<" - "<<nb<<endl;
}
}
cout<<"!!!!!! "<<curr<<endl;*/
}
for(int i=0;i<n;i++)
for(auto it=s[i].begin(); it!=s[i].end(); it++)
{
int nb=*it;
//cout<<i<<" - "<<nb<<endl;
if(i<nb)Bridge(i,nb);
}
}
