#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 10;
int pai[MAXN][5], sz[MAXN][5];
int deg[MAXN];
int good[MAXN], ciclo[5];
int ciclo_geral[MAXN];
vector<int> adj[MAXN];
int n;
int get(int v, int x){
if(v == pai[v][x]) return v;
return pai[v][x] = get(pai[v][x], x);
}
void dsu_union(int a, int b, int x){
a = get(a, x);
b = get(b, x);
if(sz[a][x] > sz[b][x]) swap(a, b);
pai[a][x] = b;
sz[b][x] += sz[a][x];
}
vector<pair<int, int>> edges;
vector<int> cand;
int cnt_4 = 0, cnt_3 = 0;
int cnt_ciclo = 0;
pair<int, int> id_ciclo = {-1, -1};
void dsu_init(int x){
for(int i=0; i<n; i++) pai[i][x] = i, sz[i][x] = 1;
ciclo[x] = 0;
for(auto [a, b] : edges){
if(a == cand[x] || b == cand[x]) continue;
if(get(a, x) != get(b, x)) dsu_union(a, b, x);
else ciclo[x] = 1;
}
}
void Init(int n_){
n = n_;
cand.clear();
edges.clear();
for(int j=0; j<5; j++) dsu_init(j);
for(int i=0; i<n; i++){
adj[i].clear();
deg[i] = 0;
good[i] = 1;
cand.push_back(i);
}
cnt_3 = cnt_4 = cnt_ciclo = 0;
}
void check_4(int v){
for(auto x : cand) if(x != v) good[x] = 0;
cand.clear();
cnt_ciclo = 0;
if(good[v]){
cand.push_back(v);
dsu_init(0);
}
}
void check_3(int v){
vector<int> to_add;
if(good[v]) to_add.push_back(v);
for(auto j : adj[v]) if(good[j]) to_add.push_back(j);
for(auto x : cand) good[x] = 0;
cand.clear();
cnt_ciclo = 0;
for(auto x : to_add){
cand.push_back(x);
good[x] = 1;
dsu_init(cand.size() - 1);
}
}
void Link(int a, int b){
deg[a] ++, deg[b] ++;
adj[a].push_back(b);
adj[b].push_back(a);
if(deg[a] == 4) cnt_4 ++;
if(deg[b] == 4) cnt_4 ++;
if(deg[a] == 3) cnt_3 ++;
if(deg[b] == 3) cnt_3 ++;
if(cnt_4 > 1){
for(auto x : cand) good[x] = 0;
cand.clear();
cnt_ciclo = 0;
} else if(deg[a] == 4){
check_4(a);
} else if(deg[b] == 4){
check_4(b);
}
if(deg[a] == 3) check_3(a);
if(deg[b] == 3) check_3(b);
// cand atualizado!
edges.push_back({a, b});
for(int i=0; i<min(4, (int) cand.size()); i++){
if(a == cand[i] || b == cand[i]) continue;
if(get(a, i) != get(b, i)) dsu_union(a, b, i);
else ciclo[i] = 1;
}
if(get(a, 4) != get(b, 4)) dsu_union(a, b, 4);
else{
if(ciclo_geral[get(a, 4)] == 0) cnt_ciclo ++;
ciclo_geral[get(a, 4)] = 1;
id_ciclo = {a, 4};
}
/*cout << "after link " << a << " " << b << ", cnt_ciclo = " << cnt_ciclo << "\n";
for(int i=0; i<(int) cand.size(); i++){
cout << cand[i] << " " << ciclo[i] << "\n";
}
cout << ".\n";
*/
}
int CountCritical(){
// cout << "cnt_ciclo = " << cnt_ciclo << "\n";
if(cnt_ciclo > 1) return 0;
if(cnt_3 == 0){
if(cnt_ciclo == 0) return n;
return sz[get(id_ciclo.first, id_ciclo.second)][id_ciclo.second];
}
int ans = 0;
for(int i=0; i<(int) cand.size(); i++) if(!ciclo[i]) ans ++;
return ans;
}
