#include #include #include #include using namespace std; #include class UnionFind { private: std::vector m_parents; std::vector m_sizes; public: UnionFind() = default; explicit UnionFind(size_t n) : m_parents(n) , m_sizes(n, 1) { std::iota(m_parents.begin(), m_parents.end(), 0); } int find(int i) { if (m_parents[i] == i) { return i; } return (m_parents[i] = find(m_parents[i])); } void merge(int a, int b) { a = find(a); b = find(b); if (a != b) { m_sizes[a] += m_sizes[b]; m_parents[b] = a; } } bool connected(int a, int b) { return (find(a) == find(b)); } int size(int i) { return m_sizes[find(i)]; } }; int main( void ) { int N, M; cin >> N >> M; vector in( N + 1, 0 ), out( N + 1, 0 ); UnionFind U( N + 1 ); int u, v; for( int i = 0; i < M; i++ ) { cin >> u >> v; U.merge( u, v ); in[v]++, out[u]++; } map mp; int num = 0, count = 0; for( int i = 1; i <= N; i++ ) { if( in[i] > out[i] ) { mp[U.find( i )] += in[i] - out[i]; } } set already; for( int i = 1; i <= N; i++ ) { num += max( mp[i] - 1, 0 ); if( !already.count( U.find( i ) ) && in[i] != 0 ) { already.insert( U.find( i ) ); count++; } } cout << num + count - 1 << endl; return 0; }