#include <vector>
#include <iostream>
using namespace std;
int N;
vector<int> grafo[1000005];
bool C[1000005];
bool V[1000005];
int A[6];
int K;
int inizio;
bool flag;
vector<int> P[6];
bool G[1000005];
bool f2;
int res;
void DFS(int k){
for(int f:grafo[k])
if(C[f] and !V[f]){
V[f]=true;
DFS(f);
}
int x=0;
for(int f:grafo[k])
if(C[f])
x++;
x=min(x,4);
A[x]++;
if(flag){
K++;
for(int f:grafo[k])
if(C[f]){
P[x].push_back(f);
}
}
}
void Init(int N_) {
N = N_;
}
void Link(int A, int B) {
grafo[A].push_back(B);
grafo[B].push_back(A);
}
int CountCritical() {
fill(C,C+N,true);
fill(V,V+N,false);
inizio=-1;
K=0;
for(int i=0;i<5;i++)
P[i].clear();
for(int i=0;i<N;i++)
if(!V[i]){
fill(A,A+5,0);
V[i]=true;
DFS(i);
if(!(A[0]==1 or (A[1]==2 and A[3]==0 and A[4]==0))){
if(inizio==-1)
inizio=i;
else
return 0;
}
}
if(inizio==-1)
return N;
fill(C,C+N,true);
fill(V,V+N,false);
fill(A,A+5,0);
flag=true;
V[inizio]=true;
DFS(inizio);
flag=false;
for(int i=0;i<N;i++)
C[i]=V[i];
if(A[4]>1)
return 0;
else if(A[4]==1){
fill(V,V+N,false);
C[P[4][0]]=false;
f2=true;
for(int i=0;i<N;i++)
if(C[i] and !V[i]){
fill(A,A+5,0);
V[i]=true;
DFS(i);
if(!(A[0]==1 or (A[1]==2 and A[3]==0 and A[4]==0)))
f2=false;
}
if(f2)
return 1;
else
return 0;
}
if(A[3]==0)
return K;
else if(A[3]>4)
return 0;
res=0;
fill(G,G+N,false);
for(int i:P[3]){
G[i]=true;
for(int f:grafo[i])
G[f]=true;
}
for(int p=0;p<N;p++)
if(G[p]){
fill(V,V+N,false);
C[p]=false;
f2=true;
for(int i=0;i<N;i++)
if(C[i] and !V[i]){
fill(A,A+5,0);
V[i]=true;
DFS(i);
if(!(A[0]==1 or (A[1]==2 and A[3]==0 and A[4]==0)))
f2=false;
}
if(f2)
res++;
C[p]=true;
}
return res;
}
