// ~ 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;
vector <int> adj[maxn5];
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;
//if(remver == 3)
// cout << "here " << a << ' ' << b << endl;
a = get_par(a);
b = get_par(b);
//if(remver == 3)
// cout << "and " << a << ' ' << b << endl;
if(a == b){
noans = true;
if(cy)
morecy = true;
else{
cy = true;
cynum = -par[a];
}
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 v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
dsu[1].add(v, u);
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 v = 0; v < n; v++) for(auto u : adj[v]) if(u < v)
dsu[1].add(v, u);
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);
//cout << i << ' ' << dsu[i].noans << ' ' << dsu[i].remver << endl;
}
return num;
}
if(!cy)
return n;
if(morecy)
return 0;
return cynum;
}
/*
4 7
1 3
1 2
2 3
0 3
0 2
0 1
-1
*/
