//#include "rings.h"
#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
//#define int long long
#define pb push_back
#define s second
#define f first
#define pf push_front
#define inf 100000000000000000
#define bitebi __builtin_popcountll
#define FOR( i , n ) for( int i = 0 ; i < n ; i ++ )
#define YES cout <<"YES\n"
#define NO cout << "NO\n"
#define debug cout << "Here Fine" << endl ;
#define pr pair < int , int >
#define fbo find_by_order // returns iterator
#define ook order_of_key // returns strictly less numbers than key
using namespace std ;
//#pragma GCC optimize("Ofast")
//#pragma GCC target("avx,avx2,fma")
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
const double Pi=acos(-1.0);
const double EPS=1E-8;
const int mod = 1000000007 ;
const int mod1 = 998244353 ;
const int N = 1e6 + 10 ;
mt19937 R(time(0));
map < int , int > ma , ma1 ;
vector < int > v[ N ] , vv[ N ] ;
int n , ss[ N ] , mx = 0 , cnt_3 = 0 , hs[ N ] ;
int pp[ 12 ][ N ] , rk[ 12 ][ N ] , s[ 12 ][ N ] , gd[ 12 ] , mm[ 12 ][ N ] ;
int raod[ 12 ] , sm[ 12 ] ;
vector < int > vii ;
void cr( int node , int v ){
s[ node ][ v ] = 1 ;
pp[ node ][ v ] = v ;
rk[ node ][ v ] = 1 ;
return ;
}
int find( int node , int v ){
if( pp[ node ][ v ] == v ) return v ;
return pp[ node ][ v ] = find( node , pp[ node ][ v ] ) ;
}
void unite( int node , int a , int b ){
if( rk[ node ][ a ] < rk[ node ][ b ] ) swap( a , b ) ;
if( rk[ node ][ a ] == rk[ node ][ b ] ) rk[ node ][ a ] ++ ;
pp[ node ][ b ] = a ;
s[ node ][ a ] = s[ node ][ a ] + s[ node ][ b ] ;
return ;
}
void add( int i , int A , int B ){
mm[ i ][ A ] ++ , mm[ i ][ B ] ++ ;
if( max( mm[ i ][ A ] , mm[ i ][ B ] ) >= 3 ) gd[ i ] = -1 ;
A = find( i , A ) ;
B = find( i , B ) ;
if( A == B ){
raod[ i ] ++ ;
sm[ i ] = sm[ i ] + s[ i ][ A ] ;
return ;
}
unite( i , A , B ) ;
}
void create( int node , int nd ){
FOR( i , n ) cr( node , i ) ;
FOR( i , n ){
if( i == nd ) continue ;
for( auto x : vv[ i ] ){
if( x == nd ) continue ;
// mm[ node ][ i ] ++ ;
if( x < i ) continue ;
add( node , i , x ) ;
}
}
}
void Init(int N){
n = N ;
vii.pb( -1 ) ;
create( 0 , -1 ) ;
}
void Link(int A, int B){
ss[ A ] ++ , ss[ B ] ++ ;
if( ss[ A ] > 3 ){
if( mx == 0 ){
mx = 1 ;
}
}
if( ss[ B ] > 3 ){
if( mx == 0 ){
mx = 1 ;
}
}
if( ss[ A ] == 3 && mx == 0 ){
if( vii.size() <= 4 ){
if( hs[ A ] == 0 ){
hs[ A ] = 1 ; vii.pb( A ) ;
create( vii.size() - 1 , A ) ;
}
if( hs[ B ] == 0 ){
hs[ B ] = 1 ; vii.pb( B ) ;
create( vii.size() - 1 , B ) ;
}
for( auto x : vv[ A ] ){
if( hs[ x ] == 0 && vii.size() <= 4 ){
hs[ x ] = 1 ; vii.pb( x ) ;
create( vii.size() - 1 , x ) ;
}
}
}
}
if( ss[ B ] == 3 && mx == 0 ){
if( vii.size() <= 4 ){
if( hs[ B ] == 0 ){
hs[ B ] = 1 ; vii.pb( B ) ;
create( vii.size() - 1 , B ) ;
}
if( hs[ A ] == 0 ){
hs[ A ] = 1 ; vii.pb( A ) ;
create( vii.size() - 1 , A ) ;
}
for( auto x : vv[ B ] ){
if( hs[ x ] == 0 && vii.size() <= 4 ){
hs[ x ] = 1 ; vii.pb( x ) ;
create( vii.size() - 1 , x ) ;
}
}
}
}
FOR( i , vii.size() )
if( A != vii[ i ] && B != vii[ i ] ) add( i , A , B ) ;
vv[ A ].pb( B ) ;
vv[ B ].pb( A ) ;
}
int CountCritical(){
int cnt = 0 ;
for( int i = 0 ; i < vii.size() ; i ++ ){
if( i == 0 ){
if( gd[ i ] == -1 ) continue ;
if( raod[ i ] == 0 ) return n ;
if( raod[ i ] == 1 ) return sm[ i ] ;
return 0 ;
}
if( raod[ i ] != 0 ) continue ;
if( gd[ i ] != -1 ){
// cout << vii[ i ] << " " ;
cnt ++ ;
}
}
// cout << endl ;
// if( cnt == 3 ) for( auto x : vii ) cout << x << " " ;
return cnt ;
}
