#include <bits/stdc++.h>
using namespace std;
const int MX = 1e6 + 5;
int N, deg[MX], cy, fl;
int dd[4][MX], p[4][MX], chk[4];
vector<int> adj[MX];
int pr[MX], sz[MX];
int gp(int a) { return pr[a]?(pr[a]=gp(pr[a])):a; }
bool un(int a, int b) {
a=gp(a), b=gp(b);
if (a!=b) {
pr[b]=a;
sz[a]+=sz[b];
}
return a!=b;
}
int gp(int a, int *p) { return p[a]?(p[a]=gp(p[a], p)):a; }
bool un(int a, int b, int *p) {
a=gp(a, p), b=gp(b, p);
if (a!=b) p[b]=a;
return a!=b;
}
vector<int> al;
void add(int u, int v) {
for (int t=0; t<al.size(); t++) {
int i=al[t];
if (i==u||i==v) continue;
if (!un(u, v, p[t])) chk[t]=0;
dd[t][u]++, dd[t][v]++;
if (dd[t][u]>=3||dd[t][v]>=3) chk[t]=0;
}
}
void init(int x) {
al.emplace_back(x);
for (auto &i:adj[x]) al.emplace_back(i);
for (int i=0; i<al.size(); i++) chk[i]=1;
for (int i=1; i<=N; i++) for (auto &j:adj[i]) if (i<j) add(i, j);
}
void Init(int N) {
::N=N;
fill(sz, sz+N+1, 1);
}
void Link(int a, int b) {
a++; b++;
deg[a]++; deg[b]++;
adj[a].emplace_back(b);
adj[b].emplace_back(a);
if (!fl&°[a]==3) fl=1, init(a);
else if (!fl&°[b]==3) fl=1, init(b);
else if (!fl) {
if (!un(a, b)) {
if (cy) cy=-1;
else cy=gp(a);
}
}
else add(a, b);
}
int CountCritical() {
if (cy==-1) return 0;
else if (!fl) return cy?sz[cy]:N;
else {
int c=0;
for (int i=0; i<al.size(); i++) c+=chk[i];
return c;
}
}
