#include #define show(x) cerr << #x << " = " << x << endl using namespace std; using ll = long long; using ld = long double; constexpr ll MOD = 1000000007LL; template constexpr T INF = numeric_limits::max() / 10; #define rep(i, n) for (int i = 0; i < n; i++) class SCC { public: vector> G, rG, graph; vector vs, cmp; vector used; int V, cnt; SCC(int node_size) { V = node_size; G.resize(V), rG.resize(V); used.resize(V), cmp.resize(V); } void add_edge(int from, int to) { G[from].push_back(to); rG[to].push_back(from); } void dfs(int u) { used[u] = true; for (int v : G[u]) { if (!used[v]) { dfs(v); } } vs.push_back(u); } void dfs(int u, const int k) { used[u] = true; cmp[u] = k; for (int v : rG[u]) { if (!used[v]) { dfs(v, k); } } } int solve() { //強連結成分の数を返す fill(used.begin(), used.end(), false); rep(i, V) { if (!used[i]) { dfs(i); } } fill(used.begin(), used.end(), false); cnt = 0; for (int i = V - 1; i >= 0; i--) { if (!used[vs[i]]) { dfs(vs[i], cnt++); } } return cnt; } void make_graph() { graph.resize(cnt); rep(i, V) { for (int v : G[i]) { if (cmp[i] != cmp[v]) { graph[cmp[i]].push_back(cmp[v]); } } } } }; class tsort { public: vector> G; vector deg, res; int V; tsort(int node_size) { V = node_size; G.resize(node_size), deg.resize(node_size, 0); } void add_edge(int from, int to) { G[from].push_back(to); deg[to]++; } bool solve() { queue que; rep(i, V) { if (deg[i] == 0) { que.push(i); } } while (!que.empty()) { int p = que.front(); que.pop(); res.push_back(p); rep(i, G[p].size()) { if (--deg[G[p][i]] == 0) { que.push(G[p][i]); } } } return (*max_element(deg.begin(), deg.end()) != 0); } }; template inline ostream& operator<<(ostream& os, const vector& v) { os << "["; for (const auto& p : v) { os << p << ","; } return (os << "]" << endl); } int main() { int N, M; cin >> N >> M; SCC G(N); for (int i = 0; i < M; i++) { int g, r; cin >> g >> r; g--; for (int j = 0; j < r; j++) { int h; cin >> h; h--; G.add_edge(h, g); } } const int sz = G.solve(); vector v(sz, 0); for (int i = 0; i < N; i++) { v[G.cmp[i]]++; } G.make_graph(); tsort t(sz); for (int i = 0; i < sz; i++) { for (const int to : G.graph[i]) { t.add_edge(i, to); } } t.solve(); vector ok(sz); for (int i = 0; i < sz; i++) { ok[i] = v[i] == 1; } show(t.res); show(ok); for (int i = 0; i < sz; i++) { const int ind = t.res[i]; for (const int to : G.graph[ind]) { ok[to] = ok[to] and ok[ind]; } } cout << accumulate(ok.begin(), ok.end(), 0LL) << endl; return 0; }