import std; void main () { int N = readln.chomp.to!int; auto graph = new int[][](N, 0); auto revgraph = new int[][](N, 0); foreach (i; 0..N) { auto input = readln.split.to!(int[]); int M = input[0]; auto A = input[1..$]; A[] -= 1; foreach (j; 0..M) { graph[i] ~= A[j]; revgraph[A[j]] ~= i; } } auto scc = scc_decomposition(graph, revgraph); int L = scc.length.to!int; auto UF = UnionFind(N); foreach (cc; scc) { foreach (v; cc) { UF.unite(cc[0], v); } } auto dag = new int[][](N, 0); foreach (i; 0..N) { foreach (to; graph[i]) { if (UF.same(i, to)) continue; int u = UF.root(i), v = UF.root(to); dag[u] ~= v; } } int begin = UF.root(0); // もらうdpで判定 int[int] memo; int dp (int pos) { if (pos in memo) return memo[pos]; int res = 1; foreach (to; dag[pos]) { res = max(res, dp(to) + 1); } return memo[pos] = res; } if (dp(begin) == L) { writeln("Yes"); } else { writeln("No"); } } int[][] scc_decomposition (int[][] graph, int[][] revgraph) in { assert(graph.length == revgraph.length, "graph.length must be equal to revgraph.length"); } do { /** * assume: * 1. vertex is 0-indexed and maximum vertex number is less than graph.length * 2. if graph has edge (u, v), revgraph has edge (v, u). * * verified with: * - yosupo judge | Stringly Connected Components (https://judge.yosupo.jp/problem/scc) (LDC2/632ms/57.90Mib) * - AIZU ONLINE JUDGE | 強連結成分分解 (https://onlinejudge.u-aizu.ac.jp/problems/GRL_3_C) **/ static bool[] vis; static int[] Q; vis.length = graph.length; Q.length = 0; void dfs (int pos) { vis[pos] = true; foreach (to; graph[pos]) { if (vis[to]) continue; dfs(to); } Q ~= pos; } foreach (i; 0..graph.length) { if (!vis[i]) dfs(cast(int) i); } int[][] scc; int idx = 0; vis[] = false; void revdfs (int pos) { vis[pos] = true; foreach (to; revgraph[pos]) { if (vis[to]) continue; revdfs(to); } scc[idx] ~= pos; } foreach_reverse (q; Q) { if (vis[q]) continue; scc ~= new int[](0); revdfs(q); idx++; } return scc; } class UnionFind_Array { /* * VERYFYIED * - uniteとsame : yosupo judge (https://judge.yosupo.jp/problem/unionfind) * * UNVERYFYIED * - countGroups * - GroupSize * - enumGroups */ private: int N; int[] parent; int[] size; this (int N) in { assert(0 <= N, "N must be positive integer."); } do { this.N = N; parent = new int[](N); size = new int[](N); foreach (i; 0..N) { parent[i] = i; size[i] = 1; } } int root (int x) in { assert(0 <= x && x < N); } do { if (parent[x] == x) return x; return parent[x] = root(parent[x]); } bool same (int x, int y) in { assert(0 <= x && x < N); assert(0 <= y && y < N); } do { return root(x) == root(y); } void unite (int x, int y) in { assert(0 <= x && x < N); assert(0 <= y && y < N); } do { int larger, smaller; if (GroupSize(x) <= GroupSize(y)) { larger = root(y); smaller = root(x); } else { larger = root(x); smaller = root(y); } if (larger == smaller) return; parent[smaller] = larger; size[larger] += size[smaller]; } int countGroups () { int res = 0; foreach (i; 0..N) if (root(i) == i) res++; return res; } int GroupSize (int x) in { assert(0 <= x && x < N); } do { return size[root(x)]; } int[][] enumGroups (int x) in { assert(0 <= x && x < N); } do { int[][] mp = new int[][](N, 0); foreach (i; 0..N) { mp[root(i)] ~= i; } int[][] res; foreach (m; mp) { if (m.length == 0) continue; res ~= m; } return res; } void reset (int N = this.N) in { assert(0 <= N, "N must be positive integer."); } do { if (N != this.N) { this.N = N; parent.length = size.length = N; } foreach (i; 0..N) { parent[i] = i; size[i] = 1; } } } auto UnionFind (int N) { return new UnionFind_Array(N); }