#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define double long double
#define FOR(i, l, r, d) for(int i=(l); i<=(r); i+=(d))
#define szof(x) ((int)(x).size())
#define vi vector<int>
#define pii pair<int, int>
#define F first
#define S second
#define pb push_back
#define eb emplace_back
#define mkp make_pair
const int MAX = 1000010;
int n;
vi edge[MAX];
int deg[MAX];
int p[MAX], sz[MAX];
set<int> check;
int deg3, deg4, cycs, cyclen;
struct DSU{
int p[MAX], sz[MAX];
void init(){
FOR(i, 0, n-1, 1){
p[i] = i;
sz[i] = 1;
}
}
int findp(int v){
if(v == p[v]) return v;
return p[v] = findp(p[v]);
}
bool uni(int u, int v){
int pu = findp(p[u]);
int pv = findp(p[v]);
if(pu == pv) return 0;
if(sz[pu] >= sz[pv]){
p[pv] = pu;
sz[pu] += sz[pv];
}
else{
p[pu] = pv;
sz[pv] += sz[pu];
}
return 1;
}
};
DSU G_now, G_check;
void Init(int N){
n = N;
FOR(i, 0, n-1, 1){
check.insert(i);
}
G_now.init();
}
void upd_check(vi val){
set<int> ret;
for(int i : val){
if(check.find(i) != check.end()) ret.insert(i);
}
check = ret;
}
void Link(int u, int v){
edge[u].pb(v);
edge[v].pb(u);
deg[u]++;
deg[v]++;
if(deg[u] == 3) deg3++, upd_check({u, edge[u][0], edge[u][1], edge[u][2]});
if(deg[v] == 3) deg3++, upd_check({v, edge[v][0], edge[v][1], edge[v][2]});
if(deg[u] == 4) deg3--, deg4++, upd_check({u});
if(deg[v] == 4) deg3--, deg4++, upd_check({v});
if(deg3 + deg4 == 0 and G_now.findp(u) == G_now.findp(v)){
G_now.uni(u, v);
cycs++;
cyclen += G_now.sz[G_now.findp(u)];
}
G_now.uni(u, v);
}
int CountCritical(){
if(deg3 + deg4 == 0){
if(cycs == 0) return n;
else if(cycs == 1) return cyclen;
else return 0;
}
else{
int ret = 0;
for(int v : check){
bool AC = 1;
G_check.init();
FOR(uu, 0, n-1, 1){
if(uu == v) continue;
for(int vv : edge[uu]){
if(vv == v or uu < vv) continue;
if(!G_check.uni(uu, vv)) AC = 0;
}
}
if(AC) ret++;
//cerr<<"check "<<v<<": "<<AC<<endl;
}
return ret;
}
}
