#include <bits/stdc++.h>
using namespace std;
#define sz(v) (int)v.size()
#define fi first
#define sc second
const int MAXN = 1e6+5;
vector<int> adj[MAXN];
int v[MAXN], p[MAXN], tam[MAXN], dist[MAXN], n, qtd;
vector< pair<int,int> > b;
void Init(int N_) {
n = N_;
}
void Link(int a, int b) {
adj[a].push_back(b);
adj[b].push_back(a);
}
void dfs(int s){
vector<int> temp;
for(int viz : adj[s])
if(dist[viz] && dist[viz] < dist[s] && viz != p[s]){
for(int j = sz(b)-1; j >= 0; j--){
if(dist[b[j].fi] < dist[viz])break;
if(dist[b[j].sc] < dist[viz]){
v[s]++; v[viz]++;
v[p[b[j].fi]]--;
if(p[b[j].sc] != -1)v[p[b[j].sc]]--;
}else{
v[s]++;
if(p[viz] != -1)v[viz]--;
v[p[b[j].fi]]--;
v[b[j].sc]++;
}
qtd++;
}
v[s]++;
if(p[viz] != -1)v[p[viz]]--;
qtd++;
temp.push_back(viz);
}
for(int i = 0; i < sz(temp); i++)b.emplace_back(s,temp[i]);
for(int viz : adj[s])
if(!dist[viz]){
p[viz] = s;
dist[viz] = dist[s]+1;
dfs(viz);
v[s] += v[viz];
}
for(int i = 0; i < sz(temp); i++)b.pop_back();
}
int CountCritical() {
qtd = 0;
for(int i = 0; i < n; i++){
dist[i] = 0;
v[i] = 0;
p[i] = -1;
}
for(int i = 0; i < n; i++)
if(!dist[i]){
dist[i] = 1;
dfs(i);
}
for(int i = 0; i < n; i++){
if(sz(adj[i]) >= 4){
qtd++; v[i]++;
}else if(sz(adj[i]) == 3){
qtd++; v[i]++;
for(int viz : adj[i])v[viz]++;
}
}
int ans = 0;
for(int i = 0; i < n; i++)
if(v[i] == qtd)ans++;
return ans;
}
