#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,t=1;
vector<int> vec[MX];
multiset<int,greater<int> > comp[MX];
int vis[MX];
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,int k=0){
vis[node]=t;
if(!k){
id[node]=idx;
comp[idx].insert(degree[node]);
}
for(auto it:vec[node])
if(vis[it]!=t)dfs(it,k);
}
int gimme(int node){
vis[node]=t;
int h=0;
for(auto it:vec[node])
if(vis[it]!=t)dfs(it,1),h++;
return h;
}
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]!=t)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;
int one=0,zero=0,nb=0;
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]--;
if(!degree[it])zero++;
//else if(degree[it]==2)nb--;
comp[id[i]].insert(degree[it]);
}
if(sz(comp[id[i]])<=2)bad=0;
else if((*comp[id[i]].begin())<=2){
t++;
auto it=comp[id[i]].lower_bound(1);
while(it!=comp[id[i]].end()){
if(*it)one++;
else break;
it++;
}
/*cerr<<"deg : "<<degree[i]<<"\n";
cerr<<i<<" "<<one<<" "<<zero<<"\n";*/
if(N<=5000){
nb=gimme(i);
if(!(one&1) && ((one/2 + zero)==nb))bad=0;
}
else if(!(one&1))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;
}
