#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int deg[MAXN], marc[MAXN], cur_deg[MAXN], saiu[MAXN];
vector<int> adj[MAXN];
int n;
void Init(int n_){
n = n_;
for(int i=0; i<n; i++){
adj[i].clear();
deg[i] = 0;
}
}
void Link(int a, int b){
adj[a].push_back(b);
adj[b].push_back(a);
deg[a] ++, deg[b] ++;
}
bool ciclo = false;
int cur_sz;
void dfs(int v, int p, int x){
marc[v] = 1;
cur_sz ++;
for(auto u : adj[v]){
if(!marc[u] && u != x){
dfs(u, v, x);
} else if(u != p && marc[u] && !saiu[u] && u != x){
ciclo = true;
}
}
saiu[v] = 1;
}
int CountCritical(){
for(int i=0; i<n; i++){
marc[i] = saiu[i] = 0;
}
for(int i=0; i<n; i++){
cur_deg[i] = deg[i];
}
pair<int, int> max_deg = {-1, -1};
for(int i=0; i<n; i++){
if(cur_deg[i] > max_deg.first){
max_deg = {cur_deg[i], i};
}
}
if(max_deg.first < 3){
// so me importo com ciclos:
int cnt_ciclos = 0;
int sz = 0;
for(int i=0; i<n; i++){
if(!marc[i]){
ciclo = false;
cur_sz = 0;
dfs(i, i, -1);
if(ciclo){
sz = cur_sz;
cnt_ciclos ++;
}
}
}
if(cnt_ciclos > 1){
// tem mais de uma componente com ciclos
return 0;
}
if(cnt_ciclos == 0) return n;
return sz;
}
vector<int> v = {max_deg.second};
if(max_deg.first <= 3) for(auto j : adj[max_deg.second]) v.push_back(j);
int ans = 0;
for(auto x : v){
for(int i=0; i<n; i++) cur_deg[i] = deg[i], marc[i] = saiu[i] = 0;
cur_deg[x] = 0;
for(auto j : adj[x]){
cur_deg[j] --;
}
bool ok = true;
for(int i=0; i<n; i++){
if(!marc[i] && i != x){
ciclo = false;
dfs(i, i, x);
if(ciclo) ok = false;
}
}
for(int i=0; i<n; i++){
if(cur_deg[i] > 2){
ok = false;
}
}
if(ok) ans ++;
}
return ans;
}
