#include "bits/stdc++.h"
using namespace std;
int N;
struct dsu {
bool cycle[1000010];
int head[1000010];
int tail[1000010];
int par[1000010];
int len[1000010];
int cycle_cnt;
int cycle_sum;
bool bad;
int no_of_nodes;
int del_node;
void init (int n) {
no_of_nodes = n;
del_node = -1;
for(int i = 0; i < no_of_nodes; i++) {
cycle[i] = false;
head[i] = tail[i] = par[i] = i;
len[i] = 1;
}
cycle_cnt = 0;
cycle_sum = 0;
bad = false;
}
int root(int x) {
if(x == par[x]) return par[x];
return par[x] = root(par[x]);
}
void add(int x, int y) {
if(del_node == x || del_node == y) return ;
if(bad) return ;
int p = root(x);
int q = root(y);
if(p == q) {
if(cycle[p]) {
bad = true;
return ;
} else if(head[p] == x && tail[p] == y) {
cycle_cnt += 1;
cycle_sum += len[p];
cycle[p] = true;
} else if (head[p] == y && tail[p] == x) {
cycle_cnt += 1;
cycle_sum += len[p];
cycle[p] = true;
} else {
bad = true;
return ;
}
} else {
if(cycle[p] || cycle[q]) {
bad = true;
return ;
}
if(len[p] > len[q]) {
swap(p, q);
swap(x, y);
}
par[p] = q;
len[q] += len[p];
if(x == head[p]) {
if(y == head[q]) {
head[q] = tail[p];
} else if (y == tail[q]) {
tail[q] = tail[p];
} else {
bad = true;
return ;
}
} else if (x == tail[p]) {
if(y == head[q]) {
head[q] = head[p];
} else if (y == tail[q]) {
tail[q] = head[p];
} else {
bad = true;
return ;
}
} else {
bad = true;
return ;
}
}
}
int count() {
if(bad) return 0;
if(cycle_cnt <= 1) {
if(cycle_cnt == 1) return cycle_sum;
else return no_of_nodes;
}
return 0;
}
} T[4];
int deg[1000010];
vector <int> l, r;
bool found_cand;
void Init(int N_) {
N = N_;
T[0].init(N);
for(int i = 0; i < N; i++) {
deg[i] = 0;
}
l.clear(); r.clear();
found_cand = false;
}
void Link(int A, int B) {
if(found_cand) {
for(int i = 0; i < 4; i++) {
T[i].add(A, B);
}
return ;
}
++deg[A]; ++deg[B];
l.emplace_back(A);
r.emplace_back(B);
if(deg[A] == 3 || deg[B] == 3) {
vector <int> v;
int can = deg[A] == 3 ? A : B;
v.emplace_back(can);
for(int i = 0; i < (int) l.size(); i++) {
if(l[i] == can || r[i] == can) {
v.emplace_back(l[i] ^ r[i] ^ can);
}
}
for(int i = 0; i < 4; i++) {
T[i].init(N);
T[i].del_node = v[i];
}
found_cand = true;
} else {
T[0].add(A, B);
}
if(found_cand) {
for(int i = 0; i < (int)l.size(); i++) {
Link(l[i], r[i]);
}
l.clear(); r.clear();
}
}
int CountCritical() {
if(found_cand) {
int ans = 0;
for(int i = 0; i < 4; i++) {
if(T[i].cycle_cnt == 0 && !T[i].bad) {
++ans;
}
}
return ans;
}
return T[0].count();
}
