#include <string.h>
#define N 1000000
#define M 1000000
int find(int *ds, int i) {
return ds[i] < 0 ? i : (ds[i] = find(ds, ds[i]));
}
int join(int *ds, int i, int j) {
i = find(ds, i);
j = find(ds, j);
if (i == j)
return 0;
if (ds[i] > ds[j])
ds[i] = j;
else {
if (ds[i] == ds[j])
ds[i]--;
ds[j] = i;
}
return 1;
}
char critical[4]; int uu[4], ds[4][N], dd[4][N], adj[N][3], ii[M], jj[M], n, m, cnt, mode;
void Init(int n_) {
n = n_, cnt = n, mode = 0;
memset(ds[0], -1, n * sizeof *ds[0]);
}
void mode1(int i) {
int j;
mode = 1, cnt = 0;
for (j = 0; j < n; j++)
if (find(ds[0], j) == i)
cnt++;
}
void mode2(int i) {
int h;
mode = 2;
for (h = 0; h < 4; h++) {
uu[h] = h < 3 ? adj[i][h] : i, critical[h] = 1;
memset(ds[h], -1, n * sizeof *ds[h]);
memset(dd[h], 0, n * sizeof *dd[h]);
}
while (m--) {
int i = ii[m], j = jj[m];
for (h = 0; h < 4; h++) {
int u = uu[h];
if (i == u || j == u)
continue;
if (++dd[h][i] > 2)
critical[h] = 0;
if (++dd[h][j] > 2)
critical[h] = 0;
if (!join(ds[h], i, j))
critical[h] = 0;
}
}
}
void mode3() {
mode = 3, cnt = 0;
}
void Link(int i, int j) {
if (mode <= 1) {
ii[m] = i, jj[m] = j, m++;
adj[i][dd[0][i]++] = j, adj[j][dd[0][j]++] = i;
if (dd[0][i] > 2)
mode2(i);
else if (dd[0][j] > 2)
mode2(j);
else if (!join(ds[0], i, j)) {
if (mode == 0)
mode1(i);
else
mode3();
}
} else if (mode == 2) {
int h;
for (h = 0; h < 4; h++) {
int u = uu[h];
if (i == u || j == u)
continue;
if (++dd[h][i] > 2)
critical[h] = 0;
if (++dd[h][j] > 2)
critical[h] = 0;
if (!join(ds[h], i, j))
critical[h] = 0;
}
}
}
int CountCritical() {
if (mode == 2) {
int h;
cnt = 0;
for (h = 0; h < 4; h++)
if (critical[h])
cnt++;
}
return cnt;
}
