#include<bits/stdc++.h>
using namespace std;
#define f first
#define s second
#define pii pair<int,int>
const int N = 1000000 + 5;
int n, sz = 0, h[N];
int cycle[7],tried[6] , rem[7], stop = 0, p[N][7], built[N];
pii deg;
vector<int> V[7][N];
void Init(int N_) {
n = N_;
for(int i = 0; i < n; i++) {
for(int t = 0; t < 6; t++) {
p[i][t] = i;
}
}
}
int find(int a, int t) {
return (p[a][t] == a ? p[a][t] : p[a][t] = find(p[a][t], t));
}
void merge(int a,int b, int t) {
a = find(a, t); b = find(b, t);
if(a == b) return;
p[a][t] = b;
return;
}
void dfs(int a, int p) {
h[a] = h[p] + 1;
for(int i = 0; i < V[5][a].size(); i++) {
if(V[5][a][i] == p) continue;
if(sz) return;
if(h[V[5][a][i]]) {
sz = h[a] - h[V[5][a][i]] + 1;
return;
} else dfs(V[5][a][i], a);
}
}
void add(int a, int b, int t) {
if(a == rem[t] || b == rem[t]) return;
V[t][a].push_back(b); V[t][b].push_back(a);
tried[t] = max(tried[t], max((int)V[t][b].size(),(int) V[t][b].size()));
if(find(a, t) == find(b, t)) cycle[t] = 1;
else merge(a, b, t);
return;
}
void Link(int a, int b) {
if(stop) return;
V[5][a].push_back(b); V[5][b].push_back(a);
deg = max(deg, {V[5][a].size(), a});
deg = max(deg, {V[5][b].size(), b});
if(find(a, 5) != find(b, 5)) {
merge(a, b, 5);
}
else {
if(!cycle[5]) {
merge(a, b, 5);
dfs(a, -1);
cycle[5] = a + 1;
}
else if(find(a, 5) != find(cycle[5] - 1, 5)) {
stop = 1;
}
}
if(built[0]) {
built[0] = 1;
add(a, b, 0);
}
if(built[1]) {
built[1] = 1;
for(int i = 1; i <= 4; i++) add(a, b, i);
}
}
void build(int t) {
int u = rem[t];
for(int i = 0; i < n; i++) {
if(u == i) continue;
for(int j = 0; j < V[5][i].size(); j++) {
int v = V[5][i][j];
if(v == u || v < i) continue;
if(find(v, t) == find(i, t)) cycle[t] = 1;
merge(i, v, t);
V[t][i].push_back(v); V[t][v].push_back(i);
}
}
for(int i = 0; i < n; i++) tried[t] = max(tried[t], (int)V[t][i].size());
}
int CountCritical() {
if(stop) return 0;
if(!cycle[5] && deg.f <= 2) return n;
if(deg.f <= 2) return sz;
if(deg.f >= 4) {
if(!built[0]) {
rem[0] = deg.s;
build(0);
}
if(tried[0] <= 2 && !cycle[0]) return 1;
stop = 1;
return 0;
}
if(!built[1]) {
rem[1] = deg.s;
for(int i = 0; i < V[5][rem[1]].size(); i++) {
rem[i + 2] = V[5][rem[1]][i];
}
for(int i = 1; i <= 4; i++) {
build(i);
}
}
int cn = 0;
for(int i = 1; i <= 4; i++) {
if(tried[i] <= 2 && !cycle[i]) cn++;
}
if(!cn) stop = 1;
return cn;
}
