#include <bits/stdc++.h>
using namespace std;
const int N = 1e6 + 42;
struct UF {
bool isChain = true, tree[N];
int par[N], deg[N], diff[N], sz[N], nbCycle = 0, total = 0;
void init(int n) {
for(int i = 0; i < n; i++) {
sz[i] = 1;
par[i] = i;
deg[i] = 0;
diff[i] = -1;
tree[i] = true;
}
}
int F(int i) {
if(par[i] == i)
return i;
return par[i] = F(par[i]);
}
int U(int a, int b) {
deg[a]++;
deg[b]++;
int d = max(deg[a], deg[b]);
if(d > 2)
isChain = false;
a = F(a), b = F(b);
if(a == b) {
if(tree[a]) {
total += sz[a];
nbCycle++;
}
diff[a]++;
isChain = false;
tree[a] = false;
return d;
}
if(sz[b] < sz[a])
swap(a, b);
par[a] = b;
sz[b] += sz[a];
diff[b] += diff[a] + 1;
if(diff[b] != -1)
isChain = false;
return d;
}
};
UF uf[5];
vector<int> adj[N];
int n, maxi = 0, nbCrit, no[5];
void create(int i, int iNot) {
no[i] = iNot;
for(int j = 0; j <= n; j++)
if(j != no[i])
for(int k : adj[j])
if(k != no[i] && j < k)
uf[i].U(j, k);
}
void Init(int N_) {
n = N_;
nbCrit = N_;
for(int i = 0; i < 5; i++)
uf[i].init(N_);
}
void Link(int A, int B) {
adj[A].push_back(B);
adj[B].push_back(A);
int newMax = uf[0].U(A, B);
if(maxi == 3) {
nbCrit = 0;
for(int i = 1; i < 5; i++) {
if(A != no[i] && B != no[i])
uf[i].U(A, B);
if(uf[i].isChain)
nbCrit++;
}
} else {
if(newMax == 3) {
maxi = newMax;
int imax = A;
if(uf[0].deg[A] < uf[0].deg[B])
imax = B;
create(1, imax);
for(int j = 0; j < 3; j++)
create(j + 2, adj[imax][j]);
nbCrit = 0;
for(int i = 1; i < 5; i++)
if(uf[i].isChain)
nbCrit++;
} else {
if(uf[0].nbCycle == 0) {
nbCrit = n;
} else if(uf[0].nbCycle == 1) {
nbCrit = uf[0].total;
} else {
nbCrit = 0;
}
}
}
}
int CountCritical() {
return nbCrit;
}
