#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e6+20;
int N,cnt,casenum,cycnum,cycl,deg[MAXN],ha[MAXN],hb[MAXN];
vector<int> adj[MAXN];
struct dsu{
int rep[MAXN],sz[MAXN];
void init(int n){
for(int i = 0;i<n;++i){
rep[i] = i;
sz[i] = 1;
}
}
int gro(int x){
return sz[finden(x)];
}
int finden(int x){
return (rep[x] = (rep[x] == x) ? x : finden(rep[x]));
}
bool unite(int x, int y){
x = finden(x); y = finden(y);
if(x == y) return false;
sz[y] += sz[x]; rep[x] = y;
return true;
}
}DSU;
struct fall{
dsu D; int deg[MAXN]; bool ok = true; int u;
void init(int u){
fall::u = u;
D.init(N); fill(deg,deg+N,0);
for(int i = 0;i<cnt;++i){
int a = ha[i], b = hb[i];
if(a == u || b == u) continue;
deg[a]++; deg[b]++;
if(!D.unite(a,b)){
ok = false;
}
if(deg[a] >= 3 || deg[b] >= 3){
ok = false;
}
}
}
void link(){
int i = cnt-1;
int a = ha[i], b = hb[i];
if(a == u || b == u) return;
deg[a]++; deg[b]++;
if(!D.unite(a,b)){
ok = false;
}
if(deg[a] >= 3 || deg[b] >= 3){
ok = false;
}
}
bool check(){
return ok;
}
}falls[4];
void Init(int n){
N = n;
DSU.init(N);
}
bool f = false;
void Link(int a, int b){
ha[cnt] = a; hb[cnt] = b; deg[a]++; deg[b]++; cnt++;
adj[a].push_back(b); adj[b].push_back(a);
if(f){
for(int i = 0;i<casenum;++i) falls[i].link();
return;
}
int u = -1;
if(deg[a] >= 3) u = a;
if(deg[b] >= 3) u = b;
if(u == -1){
if(!DSU.unite(a,b)){
cycnum++;
cycl += DSU.gro(a);
}
return;
}
f = true;
falls[casenum++].init(u);
for(auto v : adj[u]){
falls[casenum++].init(v);
}
}
int CountCritical(){
if(f){
int ans = 0;
for(int i = 0;i<casenum;++i){
if(falls[i].check()){
ans++;
}
}
return ans;
}
if(cycnum >= 2) return 0;
if(cycnum == 1) return cycl;
return N;
}
