#include<bits/stdc++.h>
using namespace std;
#define REP(i, n) for(int i = 0; i < n; i++)
template<class T> int size(T && a) { return (int) a.size(); }
struct Graph {
vector<vector<int>> adj;
vector<int> rep;
int excluded = -1;
int find(int x) {
return rep[x] < 0 ? x : find(rep[x]);
}
vector<int> bicomp;
int get_cycle() {
return -rep[find(bicomp[0])];
}
void join(int x, int y) {
x = find(x), y = find(y);
if(x == y) {
bicomp.emplace_back(x);
return;
}
rep[x] += rep[y];
rep[y] = x;
}
int deg = 0;
void add_edge(int a, int b) {
adj[a].emplace_back(b);
adj[b].emplace_back(a);
deg = max(deg, size(adj[a]));
deg = max(deg, size(adj[b]));
join(a, b);
}
Graph(int n = 0, int e = -1) : adj(n), rep(n, -1), excluded(e) {}
};
int n;
Graph graph;
vector<Graph> without;
void Init(int N) {
n = N;
graph = Graph(n);
}
void Link(int A, int B) {
if(graph.deg < 3) {
graph.add_edge(A, B);
if(graph.deg == 3) {
if(size(graph.adj[A]) != 3)
swap(A, B);
vector<int> crit = {A};
for(int u : graph.adj[A])
crit.emplace_back(u);
for(int x : crit) {
without.emplace_back(n, x);
auto &g = without.back();
REP(v, n) for(int u : graph.adj[v]) {
if(u < v && v != x && u != x)
g.add_edge(v, u);
}
}
}
}
else {
for(auto &g : without)
if(g.excluded != A && g.excluded != B)
g.add_edge(A, B);
}
}
int CountCritical() {
if(graph.deg < 3) {
int bc = size(graph.bicomp);
if(bc == 0) return n;
if(bc == 1) return graph.get_cycle();
return 0;
}
else {
int ret = 0;
for(auto &g : without) {
if(size(g.bicomp) == 0 && g.deg < 3)
ret++;
}
return ret;
}
}
