#include <bits/stdc++.h>
using namespace std;
vector<array<int, 2>> g;
int N, p;
struct Solver {
int e[1<<20], d[1<<20] = {};
int maxDeg = 0, cycle = -1, rem = -1;
int find(int u){
return e[u] < 0 ? u : e[u] = find(e[u]);
}
void add(int u, int v) {
if(u == rem || v == rem) return;
maxDeg = max({maxDeg, ++d[u], ++d[v]});
if((u = find(u)) == (v = find(v))) {
cycle = cycle >= 0 ? N : u;
} else {
if(e[u] > e[v]) swap(u, v);
e[u] += e[v], e[v] = u;
}
}
int get() {
if(maxDeg > 2) return 0;
return cycle >= 0 ? e[cycle] : N;
}
} s[5];
void Init(int N_) {
N = N_;
s[0].get();
for(int i = 0; i < 5; i++)
fill(s[i].e, s[i].e+N, -1);
}
void Link(int A, int B) {
g.push_back({A, B});
if(!p) {
s[0].add(A, B);
if(s[0].maxDeg > 2) {
for(int i = 0; i < N; i++)
if(s[0].d[i] > 2) s[p=1].rem = i;
for(auto &[u, v] : g) {
if(u == s[1].rem) s[++p].rem = v;
if(v == s[1].rem) s[++p].rem = u;
}
for(int i = 1; i < 5; i++)
for(auto &[u, v] : g)
s[i].add(u, v);
}
} else {
for(int i = 1; i < 5; i++)
s[i].add(A, B);
}
}
int CountCritical() {
int res = 0;
if(!p) res = abs(s[0].get());
else {
for(int i = 1; i < 5; i++)
res += s[i].get() > 0;
}
return res;
}
