#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6 + 11;
int N, M;
int deg[MAXN], a[MAXN], b[MAXN];
vector<int> G[MAXN];
struct DSU{
int dsu[MAXN], sz[MAXN];
void init(int n){
for(int i = 0; i < n; i++) dsu[i] = i, sz[i] = 1;
}
int f(int x){
return x == dsu[x] ? x : dsu[x] = f(dsu[x]);
}
int size(int x){
return sz[f(x)];
}
bool g(int x, int y){
x = f(x), y = f(y); if(x == y) return false;
dsu[x] = y; sz[y] += sz[x]; return true;
}
} dsu;
struct Case{
int v; DSU dsu; bool ok; int deg[MAXN];
void init(int v){
Case::v = v;
ok = true; dsu.init(N);
fill(deg, deg + N, 0);
for(int i = 0; i < M; i++){
if(a[i] == v || b[i] == v) continue;
deg[a[i]]++; deg[b[i]]++;
if(deg[a[i]] >= 3 || deg[b[i]] >= 3)
ok = false;
if(!dsu.g(a[i], b[i]))
ok = false;
}
};
void link(){
int i = M - 1;
if(a[i] == v || b[i] == v) return;
deg[a[i]]++; deg[b[i]]++;
if(deg[a[i]] >= 3 || deg[b[i]] >= 3)
ok = false;
if(!dsu.g(a[i], b[i]))
ok = false;
}
bool isCritical(){
return ok;
}
} cases[4];
int caseCount = 0;
void Init(int N_) {
N = N_; dsu.init(N);
}
bool byCase = false;
int cycleCount = 0, cycleLength = 0;
void Link(int A, int B) {
deg[A]++; deg[B]++; a[M] = A, b[M] = B, M++;
G[A].push_back(B); G[B].push_back(A);
if(byCase){
for(int i = 0; i < caseCount; i++) cases[i].link();
return;
}
int v = -1; if(deg[A] >= 3) v = A; if(deg[B] >= 3) v = B;
if(v == -1){
bool b = dsu.g(A, B);
if(!b) cycleCount++, cycleLength += dsu.size(A);
return;
}
byCase = true;
cases[caseCount++].init(v);
for(auto u : G[v]){
cases[caseCount++].init(u);
}
}
int CountCritical() {
int ans = 0;
if(byCase){
for(int i = 0; i < caseCount; i++) ans += cases[i].isCritical();
}else{
if(cycleCount >= 2) ans = 0;
else if(cycleCount == 1) ans = cycleLength;
else ans = N;
}
return ans;
}
