// ~ Be Name Khoda ~ //
#include <bits/stdc++.h>
//#pragma GCC optimize ("O3")
//#pragma GCC target("avx2")
//#pragma GCC optimize("unroll-loops,Ofast")
using namespace std;
typedef long long ll;
#define pb push_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define fi first
#define se second
const int maxn = 1e6 + 10;
const int maxn5 = 1e6 + 10;
const int maxnt = 1.2e6 + 10;
const int maxn3 = 1e3 + 10;
const int mod = 1e9 + 7;
const ll inf = 1e18;
int n;
bool found = false;
bool cy = false, morecy = false, mark[maxn5];
int cynum = 0, cnt[maxn5], q[maxn5];
vector <int> adj[maxn5];
inline void calc(){
int l = 0, r = 0;
memset(mark, false, sizeof mark);
for(int i = 0; i < n; i++){
cnt[i] = adj[i].size();
if(cnt[i] < 2){
mark[i] = true;
q[r++] = i;
}
}
while(l < r){
int v = q[l++];
for(auto u : adj[v]) if(!mark[u]){
cnt[u]--;
if(cnt[u] < 2){
mark[u] = true;
q[r++] = u;
}
}
}
cynum = 0;
for(int i = 0; i < n; i++)
cynum += (!mark[i]);
memset(mark, false, sizeof mark);
}
struct _dsu{
int remver, par[maxn5];
bool noans;
_dsu(){
remver = -1;
noans = false;
memset(par, -1, sizeof par);
}
int get_par(int a){return par[a] < 0 ? a : par[a] = get_par(par[a]);}
inline void add(int a, int b){
if(a == remver || b == remver || a == b)
return;
a = get_par(a);
b = get_par(b);
if(a == b){
noans = true;
if(cy)
morecy = true;
else{
cy = true;
if(remver == -1)
calc();
}
return;
}
if(-par[a] < -par[b])
swap(a, b);
par[a] += par[b];
par[b] = a;
}
} dsu[6];
void Init(int N_) {
n = N_;
}
void Link(int a, int b){
adj[a].pb(b);
adj[b].pb(a);
dsu[0].add(a, b);
if(found) for(int i = 1; i < 5; i++)
dsu[i].add(a, b);
if(!found && adj[a].size() == 3){
found = true;
dsu[1].remver = a;
for(int i = 0; i < 3; i++){
dsu[i + 2].remver = adj[a][i];
for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
dsu[i + 2].add(v, u);
}
}
else if(adj[a].size() == 3){
mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
dsu[i].noans = true;
mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
}
else if(adj[a].size() == 4){
for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
dsu[i].noans = true;
}
swap(a, b);
if(!found && adj[a].size() == 3){
found = true;
dsu[1].remver = a;
for(int i = 0; i < 3; i++){
dsu[i + 2].remver = adj[a][i];
for(int v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
dsu[i + 2].add(v, u);
}
}
else if(adj[a].size() == 3){
mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = true;
for(int i = 1; i < 5; i++) if(!mark[dsu[i].remver])
dsu[i].noans = true;
mark[a] = mark[adj[a][0]] = mark[adj[a][1]] = mark[adj[a][2]] = false;
}
else if(adj[a].size() == 4){
for(int i = 1; i < 5; i++) if(dsu[i].remver != a)
dsu[i].noans = true;
}
}
int CountCritical() {
if(found){
int num = 0;
for(int i = 1; i < 5; i++)
num += (!dsu[i].noans);
return num;
}
if(!cy)
return n;
if(morecy)
return 0;
return cynum;
}
