#pragma GCC optimize("O1,O2,O3,Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
const int MAX = 1000005;
struct DSU {
vi e;
DSU(int N) {
e = vi(N, -1);
}
int root(int x) {
if (e[x] < 0) {
return x;
}
else {
e[x] = root(e[x]);
return e[x];
}
}
bool sameset(int x, int y) {
return (root(x) == root(y));
}
bool unite(int x, int y) {
x = root(x);
y = root(y);
if (x == y)
return false;
if (-e[x] < -e[y])
swap(x, y);
e[x] += e[y];
e[y] = x;
return true;
}
int size(int x) {
return -e[root(x)];
}
};
int N;
vi adj[MAX];
void Init(int N_) {
N = N_;
}
void Link(int A, int B) {
adj[A].pb(B);
adj[B].pb(A);
}
int CountCritical() {
vi sus;
for (int i = 0; i < N; i++) {
if (adj[i].size() >= 3) {
sus.pb(i);
if (adj[i].size() == 3) {
for (int x : adj[i])
sus.pb(x);
}
break;
}
}
if ((int)(sus.size()) > 0) {
int total = 0;
for (int i : sus) {
// try removing each vertex, make new adj
// to check, ensure no adj cnt is > 2
// and N - edge_cnt equals number of ccs
// removed link is a chain itself
vi adjc[N];
int cnt = 0;
for (int j = 0; j < N; j++) {
if (j == i)
continue;
for (int k : adj[j]) {
if (k != i) {
adjc[j].pb(k);
cnt++;
}
}
}
cnt /= 2;
int maxc = 0;
for (int j = 0; j < N; j++) {
maxc = max(maxc, (int)(adjc[j].size()));
}
// cout<<"cnt, maxc: "<<cnt<<" "<<maxc<<endl;
int ccs = 0;
vector<bool> vis(N, false);
for (int j = 0; j < N; j++) {
if (!vis[j]) {
ccs++;
queue<int> q;
q.push(j);
vis[j] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : adjc[x]) {
if (!vis[y]) {
q.push(y);
vis[y] = true;
}
}
}
}
}
// cout<<"ccs: "<<ccs<<endl;
if ((maxc <= 2) && (N - cnt == ccs))
total++;
}
return total;
}
else { // all vertices have degree <= 2
// all lines or cycles
int cnt = 0;
for (int j = 0; j < N; j++) {
cnt += (int)(adj[j].size());
}
cnt /= 2;
int ccs = 0;
vector<bool> vis(N, false);
for (int j = 0; j < N; j++) {
if (!vis[j]) {
ccs++;
queue<int> q;
q.push(j);
vis[j] = true;
while (!q.empty()) {
int x = q.front();
q.pop();
for (int y : adj[x]) {
if (!vis[y]) {
q.push(y);
vis[y] = true;
}
}
}
}
}
if (N - cnt == ccs) {
return N;
}
else if (N - cnt == ccs - 1) { // one cycle, find length
// given adjacency list, find the cycle
// find all components, then find # edges in comp
DSU dsu(N);
for (int i = 0; i < N; i++) {
for (int j : adj[i])
dsu.unite(i, j);
}
vector<vi> incomp(N); // N vectors
for (int i = 0; i < N; i++) {
incomp[dsu.root(i)].pb(i);
}
int ans = -1;
for (int i = 0; i < N; i++) {
if ((int)(incomp[i].size()) != 0) {
int sumd = 0;
for (int j : incomp[i])
sumd += (int)(adj[j].size());
if (sumd / 2 == (int)(incomp[i].size())) {
ans = sumd / 2;
break;
}
}
}
return ans;
}
else {
return 0;
}
}
}
