#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define X first
#define Y second
#define pii pair<int, int>
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T i, U ...j) {
cout << i << ' ', abc(j...);
}
template <typename T> void printv(T l, T r) {
for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args);
#include "grader_B.cpp"
#else
#define test(args...) void(0);
#endif
const int N = 1000000;
vector <pii> edge;
vector <int> adj[N];
int deg[N], n, mx, id[N];
bool grt, dead[4];
struct Dsu {
int dsu[N], sz[N];
bool cyc;
void init(int n) {
iota(dsu, dsu + n, 0);
fill(sz, sz + n, 1);
cyc = false;
}
int Find(int x) {
if (dsu[x] == x)
return x;
return dsu[x] = Find(dsu[x]);
}
bool Union(int u, int v) {
u = Find(u), v = Find(v);
if (u == v)
return cyc = true;
dsu[u] = v;
sz[v] += sz[u];
return false;
}
} ord, p[4];
void Init(int N) {
n = mx = N;
ord.init(n);
for (int i : {0, 1, 2, 3})
p[i].init(n);
}
void gen(int v) {
assert(deg[v] == 3);
id[0] = v;
for (int i : {1, 2, 3})
id[i] = adj[v][i - 1];
for (int i = 0; i < 4; ++i) {
int v = id[i];
for (pii A : edge) {
if (A.X != v && A.Y != v) {
p[i].Union(A.X, A.Y);
}
}
}
}
void upd(int v) {
if (deg[v] == 3) {
for (int i = 0; i < 4; ++i) {
bool is = (v == id[i]);
for (int u : adj[v])
if (u == id[i])
is = true;
dead[i] = !is;
}
} else {
for (int i = 0; i < 4; ++i) if (id[i] != v)
dead[i] = true;
}
}
void Link(int a, int b) {
deg[a]++, deg[b]++;
adj[a].pb(b), adj[b].pb(a);
if (deg[a] >= 3) {
if (!grt)
gen(a), grt = true;
else
upd(a);
}
if (deg[b] >= 3) {
if (!grt)
gen(b), grt = true;
else
upd(b);
}
if (grt) {
for (int i = 0; i < 4; ++i) if (a != id[i] && b != id[i]) {
p[i].Union(a, b);
}
} else {
edge.eb(a, b);
if (ord.Union(a, b)) {
if (mx == n)
mx = ord.sz[ord.Find(a)];
else
mx = 0;
}
}
}
int CountCritical() {
if (grt) {
int ans = 0;
for (int i = 0; i < 4; ++i) if (!dead[i])
ans += !p[i].cyc;
return ans;
} else {
return mx;
}
}
/*
7 13
-1
1 2
-1
0 5
-1
2 0
-1
3 2
-1
3 5
-1
4 3
-1
*/
