#include <iostream>
#include <algorithm>
#include <vector>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
int N;
vector<int> G[1000000];
void Init(int N_) {
N = N_;
}
void Link(int a, int b) {
G[a].pb(b);
G[b].pb(a);
}
int ord[1000000];
bool used[1000000];
int T[1000000], D[1000000];
void dfs(int x, int p, vector<int> &vs, int &all) {
used[x] = true;
ord[x] = vs.size();
vs.pb(x);
for (int t : G[x]) if (t != p) {
if (used[t]) {
if (ord[x] > ord[t]) {
// [ord[t], ord[x]]
D[t]++;
D[x]++;
T[p]++;
T[t]--;
all++;
}
continue;
}
dfs(t, x, vs, all);
}
}
void dfs2(int x, int p) {
used[x] = true;
for (int t : G[x]) if (t != p && !used[t]) {
dfs2(t, x);
T[x] += T[t];
}
}
int CountCritical() {
vector<int> vs;
rep(i, N) used[i] = false, ord[i] = -1, T[i] = 0, D[i] = 0;
int all = 0;
rep(i, N) if (!used[i]) dfs(i, -1, vs, all);
rep(i, N) used[i] = false;
rep(i, N) if (!used[i]) dfs2(i, -1);
int deg3 = 0;
auto add = [&](int d) { if (d >= 3) deg3++; };
auto rem = [&](int d) { if (d >= 3) deg3--; };
rep(i, N) add(G[i].size());
int ctr = 0;
rep(x, N) {
if (T[x] >= 2 || T[x]+D[x] != all) continue;
rem(G[x].size());
for (int t : G[x]) {
rem(G[t].size());
add(G[t].size()-1);
}
if (deg3 == 0) ctr++;
for (int t : G[x]) {
rem(G[t].size()-1);
add(G[t].size());
}
add(G[x].size());
}
return ctr;
}
