#include<bits/stdc++.h>
#pragma("03")
using namespace std;
#define pii pair<int, int>
int N;
vector<vector<int>> adj;
vector<bool> passed;
set<pii> m;
vector<int> oc;
void Init(signed N_) {
N = N_;
oc.resize(5);
adj.resize(N);
passed.resize(N, false);
for(int i= 0; i<N; i++){
m.insert({0, i});
oc[0]++;
}
}
int flored(int id){
return min(4, id);
}
void Link(signed A, signed B) {
/*m.erase({adj[A].size(), A});
m.erase({adj[B].size(), B});*/
oc[flored(adj[A].size())]--;
oc[flored(adj[B].size())]--;
adj[A].push_back(B);
adj[B].push_back(A);
oc[flored(adj[A].size())]++;
oc[flored(adj[B].size())]++;
//m.insert({adj[B].size(), B});
}
int forbiden = 0;
bool acyclic = true;
void dfs(int id, int anc){
passed[id] = true;
for(auto v: adj[id]){
if(v!=forbiden && v!=anc){
if(passed[v]){
acyclic = false;
}
else{
dfs(v, id);
}
}
}
}
bool test_crititcal(int id){
forbiden = id;
for(int i = 0; i<N; i++){
int deg =0;
if(i == id){
continue;
}
for(auto e: adj[i]){
if(e!=id){
deg++;
}
}
if(deg>2){
////cout<<"deg "<<endl;
return false;
}
}
fill(passed.begin(), passed.end(), false);
acyclic = true;
for(int i= 0; i<N; i++){
if(!passed[i] && i!=forbiden){
dfs(i, -1);
}
}
return acyclic;
}
int nbc = 0;
void nb_cycles(int u, int prev){
passed[u] = true;
for(auto v: adj[u]){
if(v==prev){
continue;
}
if(passed[v]){
nbc++;
//cout<<u<<" "<<v<<endl;
}
else{
nb_cycles(v, u);
}
}
}
pair<bool, int> find_single(int u, int a, set<int>& s){
passed[u] = true;
for(auto v: adj[u]){
if(v!=a){
if(passed[v]){
s.insert(u);
return {true, v};
}
else{
auto res = find_single(v, u, s);
if(res.second == u){
s.insert(u);
return {false, -1};
}
else{
if(res.first){
s.insert(u);
return res;
}
}
}
}
}
return {false, -1};
}
void calc_cycles(set<int>& ok){
fill(passed.begin(), passed.end(), 0);
nbc= 0;
for(int i = 0; i<N; i++){
if(!passed[i]){
nb_cycles(i,-1);
}
}
nbc/=2;
}
void find_ok_first(set<int>& ok){
/*cout<<"ok "<<endl;
for(auto e: ok){
cout<<e<<" ";
}
cout<<endl;*/
}
signed CountCritical() {
m.clear();
for(int i = 0; i<N; i++){
m.insert({adj[i].size(), i});
}
int res= 0;
if(oc[4]>1){
return 0;
}
else if(oc[4] == 1){
int cand = m.lower_bound({4, 0})->second;
if(test_crititcal(cand)){
res++;
}
return res;
}
else{
set<int> ok;
calc_cycles(ok);
if(nbc==1){
fill(passed.begin(), passed.end(), 0);
for(int i = 0; i<N; i++){
if(!passed[i]){
find_single(i,-1, ok);
}
}
}
if(oc[3]>0){
auto it = m.lower_bound({3, 0});
vector<int> off(N);
for(; it!=m.end(); ++it){
set<int> neigs;
for(auto e: adj[it->second]){
off[e]++;
}
off[it->second]++;
}
set<int> pass;
for(int i = 0; i<N; i++){
if(off[i] == oc[3]){
if(test_crititcal(i)){
pass.insert(i);
}
}
}
return pass.size();
}
else if(nbc==0){
return N;
}
return ok.size();
}
}
