#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 = 5005;
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() {
int total = 0;
for (int i = 0; i < N; i++) {
// 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;
}
