#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
const int N = 1e6+10;
// graph data
int n;
vector<pii> E, ES;
vector<int> G[N];
int dfs(int u, int p, int s, int t)
{
if (u == t)
return 1;
for (auto v : G[u]) if (v != p && (u != s || v != t)) {
int r = dfs(v, u, s, t);
if (r) return r+1;
}
return 0;
}
// dsu with copying for experimentation
bool ffc = true;
int par[N], mfcnt, firstcycle;
int root(int u) {
if (par[u] == u) return u;
return par[u] = root(par[u]);
}
inline bool merge(int u, int v) {
//fprintf(stderr, "merge(%d, %d)\n", u, v);
int u0 = u, v0 = v;
u = root(u), v = root(v);
if (u == v) {
if (++mfcnt == 1 && ffc)
firstcycle = dfs(u0, -1, u0, v0);
return false;
}
par[u] = v;
return true;
}
int _np[N], _nv[N], tick;
inline int &np(int u) {
if (_nv[u] != tick) {
_np[u] = par[u];
_nv[u] = tick;
}
return _np[u];
}
int nroot(int u) {
if (np(u) == u) return u;
return np(u) = nroot(np(u));
}
inline bool nmerge(int u, int v) {
//fprintf(stderr, "nmerge(%d, %d)\n", u, v);
u = nroot(u), v = nroot(v);
if (u == v) return false;
np(u) = v;
return true;
}
// state control (degree freq. histogram)
int cntok, cnt3, cnt4, deg[N];
pii mxdeg(0, -1);
inline void testmod(int a, int b) {
if (a <= 2) --cntok;
if (a == 3) --cnt3;
if (a >= 4) --cnt4;
if (b <= 2) ++cntok;
if (b == 3) ++cnt3;
if (b >= 4) ++cnt4;
}
// rebuild dsu with exceptions
inline bool must_skip(int u) {
if (mxdeg.first < 3)
return false;
if (u == mxdeg.second)
return true;
if (mxdeg.first == 3) {
for (auto v : G[mxdeg.second]) if (v == u)
return true;
}
return false;
}
inline void build_dsu() {
//fprintf(stderr, "rebuild dsu!\n");
ES.clear();
mfcnt = 0;
for (int i = 0; i < n; ++i)
par[i] = i;
for (auto e : E) {
int u = e.first, v = e.second;
if (must_skip(u) || must_skip(v)) {
ES.emplace_back(u, v);
//fprintf(stderr, "skip edge %d %d\n", u, v);
continue;
}
merge(e.first, e.second);
}
}
inline bool modify(int u) {
++deg[u];
testmod(deg[u]-1, deg[u]);
if (deg[u] > mxdeg.first) {
mxdeg = pii(deg[u], u);
if (mxdeg.first == 3 || mxdeg.first == 4) {
ffc = false;
return true;
}
}
return false;
}
// testing functions
bool state4 = false;
bool dead[N];
inline bool test(int u) {
//fprintf(stderr, "test(%d)\n", u);
if (dead[u]) return false;
if (!state4) {
testmod(G[u].size(), 0);
for (auto v : G[u])
testmod(G[v].size(), G[v].size()-1);
if (G[u].size() == 4) {
deg[u] = 0;
for (auto v : G[u]) --deg[v];
state4 = true;
}
}
bool ok = cnt3 == 0 && cnt4 == 0;
++tick;
if (ok && !state4) for (auto e : ES) {
if (e.first == u || e.second == u) continue;
if (!nmerge(e.first, e.second)) ok = false;
if (!ok) break;
}
if (!state4) {
testmod(0, G[u].size());
for (auto v : G[u])
testmod(G[v].size()-1, G[v].size());
}
if (!ok) dead[u] = true;
return ok;
}
// problem functions:
void Init(int n) {
//fprintf(stderr, "Init(%d)\n", n);
::n = n;
build_dsu();
}
void Link(int u, int v) {
//fprintf(stderr, "Link(%d, %d)\n", u, v);
G[u].push_back(v);
G[v].push_back(u);
if (state4 && (u == mxdeg.second || v == mxdeg.second))
return;
bool m = modify(u) | modify(v);
E.emplace_back(u, v);
if (m)
build_dsu();
else if (!must_skip(u) && !must_skip(v))
merge(u, v);
else
ES.emplace_back(u, v);
}
int CountCritical() {
//fprintf(stderr, "CountCritical()\n");
if (state4) return mfcnt == 0 && test(mxdeg.second);
if (mxdeg.first <= 2) {
if (mfcnt > 1) return 0;
else if (mfcnt == 1) return firstcycle;
else if (mfcnt == 0) return n;
}
if (mfcnt > 0) return 0;
int cnt = 0;
if (test(mxdeg.second)) ++cnt;
if (mxdeg.first == 3) {
for (auto v : G[mxdeg.second])
if (test(v)) ++cnt;
}
return cnt;
}
