#include <iostream>
#include <algorithm>
#include <vector>
#include <cassert>
#define rep(i, n) for (int i=0; i<(n); i++)
#define pb push_back
#define INF (1LL<<60)
#define all(x) (x).begin(), (x).end()
#define _1 first
#define _2 second
using namespace std;
typedef pair<int, int> P;
struct UF {
vector<int> U, R;
UF(int N) {
rep(i, N) U.pb(i), R.pb(1);
}
int find(int x) {
if (U[x]==x)return x;
return U[x] = find(U[x]);
}
void unite(int x, int y) {
x=find(x), y=find(y);
if(x==y)return;
if (R[x]<R[y])swap(x,y);
U[y]=x;
R[x]+=R[y];
}
bool same(int x, int y) {
return find(x)==find(y);
}
};
int N;
struct Tree {
UF uf;
int X;
bool dead;
Tree() :uf(0){}
Tree(int X, vector<P> edges) : uf(N), X(X), dead(false) {
for (P p : edges) add_edge(p._1, p._2);
}
void add_edge(int a, int b) {
if (dead) return;
if (a==X||b==X) return;
if (uf.same(a, b)) dead = true;
uf.unite(a, b);
}
};
vector<int> G[1000000];
UF uf(0);
bool deg012 = true;
vector<int> cycles;
Tree cand[4];
vector<P> edges;
void cand_filter(vector<int> seq) {
rep(i, 4) if (!cand[i].dead) {
bool ok = false;
for (int x : seq) if (x == cand[i].X) ok = true;
if (!ok) cand[i].dead = true;
}
}
void Init(int N_) {
N = N_;
uf = UF(N);
}
void Link(int a, int b) {
edges.pb(P(a, b));
G[a].pb(b);
G[b].pb(a);
if (!deg012) rep(i, 4) cand[i].add_edge(a, b);
if (G[a].size() < 3) swap(a, b);
if (deg012 && G[a].size() >= 3) {
deg012 = false;
cand[0] = Tree(a, edges);
cand[1] = Tree(G[a][0], edges);
cand[2] = Tree(G[a][1], edges);
cand[3] = Tree(G[a][2], edges);
}
if (G[a].size() == 3) cand_filter({a, G[a][0], G[a][1], G[a][2]});
if (G[b].size() == 3) cand_filter({b, G[b][0], G[b][1], G[b][2]});
if (G[a].size() >= 4) cand_filter({a});
if (G[b].size() >= 4) cand_filter({b});
if (deg012) {
bool same = uf.same(a, b);
uf.unite(a, b);
if (same) cycles.pb(uf.R[uf.find(a)]);
}
}
int CountCritical() {
if (deg012) {
if (cycles.size() == 0) return N;
else if (cycles.size() == 1) return cycles[0];
else return 0;
}
int s = 0;
rep(i, 4) s += !cand[i].dead;
return s;
}
