## Editorial for Bedao Grand Contest 08 - RESTRICTIONS

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

#### Code mẫu

#include <bits/stdc++.h>
using namespace std;

const int N = 200005;

int n, m, u, v, chk[N];
int cyc, dp[2 * N][2];
vector<int> stk, adj[N], bip[2 * N];

void DFS_1(int u) {
chk[u] = 1;
stk.push_back(u);
for (int v : adj[u]) {
if (chk[v] == 0) {
DFS_1(v);
} else if (chk[v] == 1) {
cyc++;
bip[v].push_back(cyc);
bip[cyc].push_back(v);
for (int i = stk.size() - 1; i >= 0; i--) {
if (stk[i] == v) {
break;
} else {
bip[stk[i]].push_back(cyc);
bip[cyc].push_back(stk[i]);
}
}
}
}
chk[u] = 2;
stk.pop_back();
}

void DFS_2(int u, int p = 0) {
int mi = n;
for (int v : bip[u]) {
if (v != p) {
DFS_2(v, u);
if (u <= n) {
// original node
dp[u][0] += dp[v][1];
dp[u][1] += min(dp[v][0], dp[v][1]);
} else {
// cycle node
dp[u][0] += min(dp[v][0], dp[v][1]);
dp[u][1] += min(dp[v][0], dp[v][1]);
mi = min(mi, max(0, dp[v][1] - dp[v][0]));
}
}
}
dp[u][1] += (u <= n ? 1 : mi);
}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
// freopen("RESTRICTIONS.inp", "r", stdin);
// freopen("RESTRICTIONS.out", "w", stdout);
cin >> n >> m;
cyc = n;
for (int i = 1; i <= m; i++) {
cin >> u >> v;
}
for (int i = 1; i <= n; i++) {
if (chk[i] == 0) {
DFS_1(i);
}
}
int ans = 0;
for (int i = n + 1; i <= cyc; i++) {
if (dp[i][1] == 0) {
DFS_2(i);
ans += dp[i][1];
}
}
cout << n - ans;
}