//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
//#include "grader.h"
#define pii pair<int,int>
#define vi vector<int>
#define vii vector<pii>
#define pb push_back
using namespace std;
const int MAXN = 1e6 + 5;
int par[MAXN], deg[MAXN], cycle = 0, cnt[MAXN], n = 0;
int mrk[MAXN];
vi cand, adj[MAXN];
struct DSU {
int par[MAXN], deg[MAXN], root = 0;
bool valid = true;
int qry(int x) {
if (!valid) return 0;
return x == par[x] ? x : par[x] = qry(par[x]);
}
void join(int u, int v) {
if (!valid) return;
u = qry(u), v = qry(v);
par[u] = v;
}
void init(int n) {
for (int i = 0; i < n; i++)
par[i] = i;
}
} e, f;
int qry(int x) {
return x == par[x] ? x : par[x] = qry(par[x]);
}
void join(int u, int v) {
u = qry(u), v = qry(v);
par[u] = v;
}
void Init(int N) {
n = N;
for (int i = 0; i < N; i++) {
par[i] = i;
cand.pb(i);
mrk[i] = 1;
}
}
void do3(int b) {
vi tmp;
for (int v: adj[b])
if (mrk[v])
tmp.pb(v);
if (mrk[b])
tmp.pb(b);
for (int v: cand)
mrk[v] = 0;
for (int v: tmp)
mrk[v] = 1;
cand = tmp;
}
int par2[MAXN];
bool fin = false;
vii edg;
void dfs(int u, int p) {
par2[u] = p;
for (int v: adj[u])
if (v != p)
dfs(v, u);
}
void addE(int u, int v) {
if (u == e.root || v == e.root || e.valid == false) return;
e.deg[u]++, e.deg[v]++;
if (e.qry(u) == e.qry(v) || e.deg[u] > 2 || e.deg[v] > 2)
e.valid = false;
e.join(u, v);
}
void addF(int u, int v) {
if (u == f.root || v == f.root || f.valid == false) return;
f.deg[u]++, f.deg[v]++;
if (f.qry(u) == f.qry(v) || f.deg[u] > 2 || f.deg[v] > 2)
f.valid = false;
f.join(u, v);
}
void Link(int a, int b) {
if (cand.empty()) return;
if (fin) {
addE(a, b);
addF(a, b);
return;
}
edg.pb({a, b});
int delta = 0;
if (qry(a) == qry(b) && cycle == 0) {
dfs(a, -1);
vi tmp = {a};
int u = b;
while (u != a) {
tmp.pb(u);
u = par2[u];
}
vi nx;
for (int i: tmp)
if (mrk[i] == 1) {
nx.pb(i);
mrk[i] = 2;
}
for (int i: cand)
mrk[i]--;
cand = nx;
}
adj[a].pb(b);
adj[b].pb(a);
if (qry(a) == qry(b)) {
delta++;
cycle++;
}
cnt[deg[a]]--;
cnt[deg[b]]--;
deg[a]++, deg[b]++;
cnt[deg[a]]++;
cnt[deg[b]]++;
if (cnt[4] > 1) {
cand = {};
return;
}
if (deg[a] > deg[b])
swap(a, b);
if (deg[b] == 3) do3(b);
if (deg[a] == 3) do3(a);
if (deg[b] == 4) {
if (!mrk[b]) {
cand = {};
return;
}
memset(mrk, 0, sizeof mrk);
mrk[b] = 1;
cand = {b};
}
join(a, b);
if (cand.empty()) return;
if (cycle > 1 && delta > 0) {
if (qry(a) != qry(cand[0])) {
cand = {};
return;
}
if (mrk[a] && mrk[b]) {
cand = {a, b};
memset(mrk, 0, sizeof mrk);
mrk[a] = 1, mrk[b] = 1;
} else if (mrk[a] || mrk[b]) {
if (mrk[a]) {
memset(mrk, 0, sizeof mrk);
mrk[a] = 1;
cand = {a};
} else {
memset(mrk, 0, sizeof mrk);
mrk[b] = 1;
cand = {b};
}
}
fin = true;
if (cand.size() == 1) {
f.valid = false;
e.init(n);
e.root = cand[0];
for (int i = 0; i < edg.size(); i++) {
int u, v;
tie(u, v) = edg[i];
if (u == cand[0] || v == cand[0]) continue;
e.deg[u]++, e.deg[v]++;
if (e.qry(u) == e.qry(v) || e.deg[u] > 2 || e.deg[v] > 2) {
cand = {};
return;
}
e.join(u, v);
}
} else {
e.init(n);
e.root = cand[0];
for (int i = 0; e.valid && i < edg.size(); i++) {
int u, v;
tie(u, v) = edg[i];
if (u == cand[0] || v == cand[0]) continue;
e.deg[u]++, e.deg[v]++;
if (e.qry(u) == e.qry(v) || e.deg[u] > 2 || e.deg[v] > 2)
e.valid = false;
e.join(u, v);
}
f.init(n);
f.root = cand[1];
for (int i = 0; f.valid && i < edg.size(); i++) {
int u, v;
tie(u, v) = edg[i];
if (u == cand[1] || v == cand[1]) continue;
f.deg[u]++, f.deg[v]++;
if (f.qry(u) == f.qry(v) || f.deg[u] > 2 || f.deg[v] > 2)
f.valid = false;
f.join(u, v);
}
}
}
}
int CountCritical() {
int ret = 0;
if (fin) {
ret += (e.valid ? 1 : 0);
ret += (f.valid ? 1 : 0);
return ret;
}
return cand.size();
}
