#include "bits/stdc++.h" using namespace std; namespace util { using ll = long long; using vl = std::vector; using pl = std::pair; constexpr long long kInf = std::numeric_limits::max() / 8; constexpr long long kMax = std::numeric_limits::max(); template inline bool UpdateMax(T &x, const U &y) { if (x < y) { x = y; return true; } return false; } template inline bool UpdateMin(T &x, const U &y) { if (x > y) { x = y; return true; } return false; } // verified inline long long Pow(long long x, long long n) { assert(n >= 0); if (x == 0) return 0; long long res = 1LL; while (n > 0) { if (n & 1) { assert(x != 0 && std::abs(res) <= kMax / std::abs(x)); res = res * x; } if (n >>= 1) { assert(x != 0 && std::abs(x) <= kMax / std::abs(x)); x = x * x; } } return res; } // verified inline long long Mod(long long n, const long long m) { // returns the "arithmetic modulo" // for a pair of integers (n, m) with m != 0, there exists a unique pair of // integer (q, r) s.t. n = qm + r and 0 <= r < |m| returns this r assert(m != 0); if (m < 0) return Mod(n, -m); if (n >= 0) return n % m; else return (m + n % m) % m; } inline long long Quotient(long long n, long long m) { // returns the "arithmetic quotient" assert((n - Mod(n, m)) % m == 0); return (n - Mod(n, m)) / m; } inline long long DivFloor(long long n, long long m) { // returns floor(n / m) assert(m != 0); if (m < 0) { n = -n; m = -m; } if (n >= 0) return n / m; else if (n % m == 0) return -(abs(n) / m); else return -(abs(n) / m) - 1; } inline long long DivCeil(long long n, long long m) { // returns ceil(n / m) assert(m != 0); if (n % m == 0) return DivFloor(n, m); else return DivFloor(n, m) + 1; } template inline T Sum(const std::vector &vec) { return std::accumulate(vec.begin(), vec.end(), T(0)); } } // namespace util using namespace util; template std::vector Deduplicate(std::vector v) { std::sort(v.begin(), v.end()); v.erase(std::unique(v.begin(), v.end()), v.end()); return v; } using Graph = std::vector>; Graph TransposeGraph(const Graph &g) { int n = (int)size(g); Graph res(n); for (int i = 0; i < n; ++i) { for (int to : g[i]) { res[to].emplace_back(i); } } return res; } // 返り値:強連結成分を表すリストのリスト(トポロジカルソート済み)・各頂点がリストの何番に入っているかを表すリスト・強連結成分を頂点とするグラフ std::tuple>, std::vector, Graph> Scc( const Graph &g) { int n = (int)size(g); std::vector time(n); std::vector seen(n); { int counter = 0; auto CalculateReachingTime = [&](auto &&self, const int s) -> void { seen[s] = true; for (int nv : g[s]) { if (seen[nv]) continue; self(self, nv); } time[s] = counter; counter++; }; for (int i = 0; i < n; ++i) { if (!seen[i]) CalculateReachingTime(CalculateReachingTime, i); } } Graph g_transpose = TransposeGraph(g); std::vector vertex_of_time(n); for (int i = 0; i < n; ++i) { vertex_of_time[time[i]] = i; } std::vector> connected_components; { std::vector transpose_seen(n, false); auto SearchInComponent = [&g_transpose, &transpose_seen]( auto &&self, const int s, std::vector &component) -> void { component.emplace_back(s); transpose_seen[s] = true; for (int nv : g_transpose[s]) { if (transpose_seen[nv]) continue; self(self, nv, component); } }; for (int t = n - 1; t >= 0; t--) { int v = vertex_of_time[t]; if (!transpose_seen[v]) { std::vector component; SearchInComponent(SearchInComponent, v, component); connected_components.emplace_back(component); } } } int c = (int)connected_components.size(); std::vector owner(n); for (int i = 0; i < c; ++i) { for (int v : connected_components[i]) { owner[v] = i; } } Graph contracted_graph(c); for (int i = 0; i < n; i++) { int from = owner[i]; for (auto v : g[i]) { int to = owner[v]; if (from != to) { contracted_graph[from].emplace_back(to); } } } for (int v = 0; v < c; ++v) { Deduplicate(contracted_graph[v]); } return {connected_components, owner, contracted_graph}; } void solve() { ll n, m; cin >> n >> m; Graph g(n); vl od(n, 0), id(n, 0); for (ll i = 0; i < m; i++) { ll a, b; cin >> a >> b; a--; b--; od[a]++; id[b]++; g[a].emplace_back(b); } ll ans = 0; for (ll i = 0; i < n; i++) { if (od[i] > id[i]) { ans += od[i] - id[i]; } } if (ans <= 1) { cout << 0 << '\n'; } else { cout << ans - 1 << '\n'; } } int main() { std::cin.tie(nullptr); std::ios::sync_with_stdio(false); std::cout << std::fixed << std::setprecision(15); solve(); return 0; }