#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define all(x) x.begin(), x.end()
#define kill(x) return cout << x << endl, 0
#define X first
#define Y second
#define endl '\n'
constexpr ll pw(ll a, ll b, ll mod) {
return (!b ? 1 :
b & 1 ? a * pw(a * a % mod, b / 2, mod) % mod :
pw(a * a % mod, b / 2, mod));
}
constexpr int N = 5e3 + 10;
constexpr int MOD = 1e9 + 7;
constexpr ll INF = 1e18;
int n, mark[N], par[N], edg[N], sz[N];
vector<int> adj[N];
bool critDFS(int u) {
int d = 0;
bool flag = true;
mark[u] = 1;
for (int v : adj[u]) if (mark[v] < 3) {
d++;
flag &= (mark[v] != 2);
if (mark[v] == 0) {
flag &= critDFS(v);
}
}
flag &= (d <= 2);
mark[u] = 2;
return flag;
}
bool check(int u) {
bool flag = true;
fill(mark, mark + N, 0);
mark[u] = 3;
for (int i = 0; i < n; i++) if (mark[i] == 0) {
flag &= critDFS(i);
}
return flag;
}
int dsufind(int u) {
return (par[u] == -1 ? u : par[u] = dsufind(par[u]));
}
void dsumerge(int u, int v) {
u = dsufind(u), v = dsufind(v);
if (u == v) {
edg[u]++;
return;
}
if (sz[v] > sz[u])
swap(u, v);
par[v] = u;
edg[u] += edg[v] + 1;
sz[u] += sz[v];
}
void Init(int N_) {
n = N_;
assert(n < N);
fill(par, par + n, -1);
fill(sz, sz + n, 1);
}
void Link(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
dsumerge(u, v);
}
int CountCritical() {
vector<int> v3, v4;
for (int i = 0; i < n; i++) {
if (adj[i].size() >= 4)
v4.push_back(i);
else if (adj[i].size() == 3)
v3.push_back(i);
}
if (v4.size() >= 2)
return 0;
if (v4.size() == 1)
return check(v4[0]);
if (v3.size() >= 1) {
int ans = check(v3[0]);
for (int v : adj[v3[0]])
ans += check(v);
return ans;
}
int t[2] = {0, 0};
for (int i = 0; i < n; i++) if (dsufind(i) == i) {
if (edg[i] == sz[i]) {
if (t[1] > 0) return 0;
t[1] = sz[i];
}
else
t[0] += sz[i];
}
return (t[1] > 0 ? t[1] : t[0]);
}
