#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#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;
struct UF {
vector<int> U, R;
UF(int N) {
rep(i, N) U.pb(i), R.pb(1);
}
int find(int x) {
if (U[x]==x)return x;
return U[x] = find(U[x]);
}
void unite(int x, int y) {
x=find(x), y=find(y);
if(x==y)return;
if (R[x]<R[y])swap(x,y);
U[y]=x;
R[x]+=R[y];
}
bool same(int x, int y) {
return find(x)==find(y);
}
};
typedef pair<int, int> P;
int N;
UF uf = NULL;
vector<int> G[1000000];
bool deg012 = true;
vector<int> cycles;
vector<int> cand;
void cand_filter(vector<int> seq) {
sort(all(seq));
int a = 0, b = 0;
vector<int> ret;
while (a<cand.size() && b<seq.size()) {
if (cand[a]==seq[b])ret.pb(cand[a]), a++, b++;
else if (cand[a]<seq[b]) a++;
else b++;
}
swap(cand, ret);
}
void Init(int N_) {
N = N_;
uf = UF(N);
rep(i, N) cand.pb(i);
}
void Link(int a, int b) {
G[a].pb(b);
G[b].pb(a);
if (G[a].size() >= 3) deg012 = false;
if (G[b].size() >= 3) deg012 = false;
if (G[a].size() == 3) cand_filter({a, G[a][0], G[a][1], G[a][2]});
if (G[b].size() == 3) cand_filter({b, G[b][0], G[b][1], G[b][2]});
if (G[a].size() >= 4) cand_filter({a});
if (G[b].size() >= 4) cand_filter({b});
if (!deg012) {
bool same = uf.same(a, b);
uf.unite(a, b);
if (same) cycles.pb(uf.R[uf.find(a)]);
}
}
int ord[1000000], low[1000000];
int R[1000000];
void dfs(int x, int p, int r) {
ord[x] = low[x] = r;
if (p == -1) R[x] = -1;
for (int t : G[x]) if (t != p) {
if (ord[t] != -1) {
low[x] = min(low[x], ord[t]);
continue;
}
dfs(t, x, r+1);
low[x] = min(low[x], low[t]);
if (p == -1 || low[t] >= ord[x]) R[x]++;
}
}
int CountCritical() {
if (deg012) {
if (cycles.size() == 0) return N;
else if (cycles.size() == 1) return cycles[0];
else return 0;
}
if (cand.size() == 0) return 0;
rep(i, N) ord[i] = low[i] = -1, R[i] = 0;
int r_def = 0;
rep(i, N) if (ord[i] == -1) dfs(i, -1, 0), r_def++;
int deg0 = 0, deg1 = 0, deg3 = 0;
auto add = [&](int d) {
if (d == 0) deg0++;
else if (d == 1) deg1++;
else if (d >= 3) deg3++;
};
auto rem = [&](int d) {
if (d == 0) deg0--;
else if (d == 1) deg1--;
else if (d >= 3) deg3--;
};
rep(i, N) add(G[i].size());
int ctr = 0;
for (int x : cand) {
rem(G[x].size());
for (int t : G[x]) {
rem(G[t].size());
add(G[t].size()-1);
}
assert(deg3 == 0);
if (2*((r_def+R[x])-deg0) == deg1) ctr++;
for (int t : G[x]) {
rem(G[t].size()-1);
add(G[t].size());
}
add(G[x].size());
}
return ctr;
}
