#include "meetings.h"
#include<bits/stdc++.h>
#define all(x) x.begin(),x.end()
#define sz(x) (int)(x.size() )
#define ll long long
using namespace std ;
int qtd ;
vector<int> sub , arr ;
vector<bool> vis , foundPlace ;
vector< vector<int> > adj ;
void dfs1(int x, int parent)
{
sub[x] = 1 ;
for(auto e : adj[x] )
{
if(vis[e] || e == parent ) continue ;
dfs1(e, x ) ;
sub[x] += sub[e] ;
}
}
int dfs2(int x, int parent )
{
for(auto e : adj[x] )
{
if( e == parent || vis[e] ) continue ;
if( sub[e] > qtd/2 ) return dfs2(e, x ) ;
}
return x ;
}
void dfs3(int x, int parent )
{
sub[x] = 1 ;
for(auto e : adj[x] )
{
if( e == parent || vis[e] ) continue ;
dfs3(e,x ) ;
sub[x] += sub[e] ;
}
}
void insertMiddle(int A, int middle, int B )
{
for(int i = 0 ; i < 2 ; i++ )
{
for(int j = 0 ; j < sz(adj[A]) ; j++ )
{
if( adj[A][j] != B ) continue ;
swap(adj[A][ sz( adj[A] )-1 ], adj[A][j] ) ;
adj[A].pop_back() ;
break ;
}
swap(A,B) ;
}
adj[A].push_back(middle) ;
adj[B].push_back(middle) ;
adj[middle].push_back(A) ;
adj[middle].push_back(B) ;
}
void createEdge(int A, int B )
{
adj[A].push_back(B) ;
adj[B].push_back(A) ;
}
void decompose( int toInsert , int x )
{
dfs1( x , -1 ) ;
qtd = sub[x] ;
int cn = dfs2(x,-1) ;
dfs3(cn,-1) ;
vector<int> children ;
for(auto e : adj[cn] )
if( !vis[e] ) children.push_back( e ) ;
sort(all(children), [&](int i, int j ) { return sub[i] < sub[j] ; } ) ;
vis[cn] = true ;
for(int i = 0 ; i < sz(children) ; i += 2 )
{
if(i+1 == sz(children) )
{
int resp = Query(children[i], toInsert, cn ) ;
if( resp == toInsert ) insertMiddle(children[i], toInsert, cn ) ;
else if( resp == cn ) createEdge(cn, toInsert) ;
else if( resp == children[i] ) decompose(toInsert, children[i] ) ;
else
{
insertMiddle(cn, resp, children[i] ) ;
createEdge(resp, toInsert) ;
foundPlace[resp] = true ;
}
return ;
}
int resp = Query(children[i], children[i+1], toInsert) ;
if(resp == cn ) continue ;
else if( resp == children[i] ) return (void)(decompose(toInsert, children[i] ) ) ;
else if( resp == children[i+1] ) return (void)(decompose(toInsert, children[i+1] ) ) ;
else if( resp == toInsert )
{
resp = Query( children[i] , cn , toInsert ) ;
if( resp == toInsert ) insertMiddle( children[i] , toInsert, cn ) ;
else insertMiddle(children[i+1], toInsert, cn ) ;
return ;
}
else
{
int resp2 = Query(children[i], cn, resp ) ;
if(resp2 == resp )
{
insertMiddle(children[i], resp, cn ) ;
createEdge(resp, toInsert) ;
foundPlace[ resp ]= true ;
}
else
{
insertMiddle(children[i+1], resp, cn ) ;
createEdge(resp, toInsert) ;
foundPlace[resp] = true ;
}
return ;
}
}
createEdge(cn, toInsert) ;
}
void Solve(int N)
{
srand( time(0) ) ;
arr.resize(N) ; iota(all(arr) , 0 ) ;
random_shuffle( all(arr) ) ;
sub.resize(N) ;
vis.resize(N) ;
foundPlace.resize(N) ;
adj.resize(N, vector<int>() ) ;
adj[ arr[0] ].push_back( arr[1] ) ;
adj[ arr[1] ].push_back( arr[0] ) ;
foundPlace[ arr[0] ] = foundPlace[ arr[1] ] = true ;
for(int i = 2 ; i < N ; i++ )
{
if(foundPlace[ arr[i] ] ) continue ;
for(int j = 0 ; j < N ; j++ ) vis[j] = false ;
decompose( arr[i] , arr[0] ) ;
foundPlace[ arr[i] ] = true ;
}
for(int i = 0 ; i < N ; i++ )
for(auto e : adj[i] )
if( i < e ) Bridge(i, e) ;
}
