#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define sz(x) (int)(x.size())
const int MX = (int)(1e6+3);
typedef pair<int,int> ii;
int N,degree[MX],id[MX],idx;
vector<int> vec[MX];
multiset<int,greater<int> > comp[MX];
bitset<MX> vis;
void Init(int N_) {
N = N_;
}
void Link(int A, int B) {
vec[A].pb(B),vec[B].pb(A);
degree[A]++,degree[B]++;
}
void dfs(int node){
vis[node]=1;
id[node]=idx;
comp[idx].insert(degree[node]);
for(auto it:vec[node])
if(!vis[it])dfs(it);
}
int CountCritical() {
idx=0;
for (int i = 0; i < N; ++i)
vis[i]=0,comp[i].clear();
for (int i = 0; i < N; ++i)
if(!vis[i])dfs(i),idx++;
set<int> good;
for (int i = 0; i < idx; ++i)
{
if(sz(comp[i])==1)good.insert(i);
else if((*comp[i].begin())<=2 && comp[i].find(1)!=comp[i].end()){
comp[i].erase(comp[i].find(1));
bool f=0;
if(comp[i].find(1)!=comp[i].end())f=1;
comp[i].insert(1);
if(f)good.insert(i);
}
}
//cerr<<idx<<","<<sz(good)<<"\n";
int ans=0;
for (int i = 0; i < N; ++i)
{
bool g=0;
if(good.find(id[i])!=good.end())good.erase(id[i]),g=1;
if(sz(good)==(idx-1)){
bool bad=1;
comp[id[i]].erase(comp[id[i]].find(degree[i]));
for(auto it:vec[i]){
comp[id[i]].erase(comp[id[i]].find(degree[it]));
degree[it]--;
comp[id[i]].insert(degree[it]);
}
if(sz(comp[id[i]])<=2)bad=0;
else if((*comp[id[i]].begin())<=2 && comp[id[i]].find(1)!=comp[id[i]].end()){
comp[id[i]].erase(comp[id[i]].find(1));
bool f=0;
if(comp[id[i]].find(1)!=comp[id[i]].end())f=1;
comp[id[i]].insert(1);
if(f)bad=0;
}
if(!bad)ans++;
for(auto it:vec[i]){
comp[id[i]].erase(comp[id[i]].find(degree[it]));
degree[it]++;
comp[id[i]].insert(degree[it]);
}
comp[id[i]].insert(degree[i]);
}
if(g)good.insert(id[i]);
}
//cerr<<"\n---------\n";
return ans;
}
