#include <bits/stdc++.h>
using namespace std;
const int N=1e6+1;
int n, cnt[N], dsu[N], sz[N];
vector<int> v[N], v2;
set<int> crit, tmp;
int vis[N], par[N];
vector<int> cyc;
int find(int x){
return dsu[x]==x? x: dsu[x]=find(dsu[x]);
}
void join(int x, int y){
x=find(x), y=find(y);
sz[y]+=sz[x];
dsu[x]=y;
}
void Init(int N_) {
n=N_;
for (int i=0; i<n; i++){
cnt[i]=0;
dsu[i]=i, sz[i]=1;
v[i].clear();
crit.insert(i);
vis[i]=0, par[i]=-1;
}
cyc.clear();
}
void setcrit(vector<int> v){
tmp.clear();
for (int i: v){
if (crit.find(i)!=crit.end()) tmp.insert(i);
}
crit=tmp;
}
void Link(int A, int B) {
cnt[A]=min(cnt[A]+1, 4), cnt[B]=min(cnt[B]+1, 4);
v[A].push_back(B);
v[B].push_back(A);
if (find(A)!=find(B)) join(A, B);
else{
// do sth
}
if (cnt[A]==3){
v2=v[A];
v2.push_back(A);
setcrit(v2);
}else if (cnt[A]==4) setcrit({A});
if (cnt[B]==3){
v2=v[B];
v2.push_back(B);
setcrit(v2);
}else if (cnt[B]==4) setcrit({B});
}
void dfs(int x, int prev=-1){
if (!cyc.empty()) return;
vis[x]=1, par[x]=prev;
for (int i: v[x]){
if (!vis[i]){
dfs(i, x);
continue;
}
if (i==prev || vis[i]==2) continue;
int t=x;
cyc.push_back(i);
while (t!=i){
cyc.push_back(t);
t=par[t];
assert(t!=-1);
}
setcrit(cyc);
}
vis[x]=2;
}
int CountCritical() {
for (int i=0; i<n; i++){
if (!vis[i]) dfs(i);
}
return crit.size();
}
