import java.io.BufferedReader; import java.io.InputStreamReader; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; import java.util.Deque; import java.util.HashSet; import java.util.List; import java.util.Set; public class Main { static List> list; public static void main(String[] args) throws Exception { BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); int n = Integer.parseInt(br.readLine()); int[] m = new int[n]; int[][] a = new int[n][]; for (int i = 0; i < n; i++) { String[] sa = br.readLine().split(" "); m[i] = Integer.parseInt(sa[0]); a[i] = new int[m[i]]; for (int j = 0; j < m[i]; j++) { a[i][j] = Integer.parseInt(sa[j + 1]) - 1; } } br.close(); SCC scc = new SCC(n); for (int i = 0; i < n; i++) { for (int j = 0; j < m[i]; j++) { scc.addEdge(i, a[i][j]); } } int[][] g = scc.scc(); DSU uf = new DSU(n); for (int i = 0; i < g.length; i++) { for (int j = 1; j < g[i].length; j++) { uf.merge(g[i][0], g[i][j]); } } list = new ArrayList<>(n); for (int i = 0; i < n; i++) { list.add(new HashSet<>()); } for (int i = 0; i < n; i++) { for (int j = 0; j < m[i]; j++) { if (!uf.same(i, a[i][j])) { list.get(uf.leader(i)).add(uf.leader(a[i][j])); } } } boolean[] vis = new boolean[n]; boolean res = dfs(uf.leader(0), vis); if (!res) { System.out.println("No"); return; } for (int i = 0; i < n; i++) { if (!vis[uf.leader(i)]) { System.out.println("No"); return; } } System.out.println("Yes"); } static boolean dfs(int x, boolean[] vis) { vis[x] = true; Set nexts = list.get(x); if (nexts.size() > 1) { return false; } if (nexts.isEmpty()) { return true; } return dfs(nexts.iterator().next(), vis); } } class SCC { /** gid[i]:頂点iが何番目の強連結成分に属しているか */ int[] gid; private final int n; private List edges; private int nowOrd, groupNum; private int[] start, low, ord; private Edge[] elist; private Deque visited; private class Edge { final int from, to; public Edge(int from, int to) { this.from = from; this.to = to; } } /** * n頂点0辺のグラフを作る。
* O(n) * * @param n 頂点数 */ public SCC(int n) { this.n = n; edges = new ArrayList<>(); } /** * fromからtoへ有向辺を追加する。
* ならしO(1) * * @param from 有向辺の始点(0≦from<n) * @param to 有向辺の終点(0≦to<n) */ void addEdge(int from, int to) { assert 0 <= from && from < n : "from=" + from; assert 0 <= to && to < n : "to=" + to; edges.add(new Edge(from, to)); } /** *
	 * 強連結成分分解
	 * 辺の本数をmとして、O(n + m)
	 * 
	 * ・全ての頂点がちょうど1つずつ、内側の配列のどれかに含まれる。
	 * ・内側の配列(1つの強連結成分)内での頂点の順序は未定義。
	 * ・外側の配列はトポロジカルソートされている。
	 * 
* * @return 強連結成分ごとの頂点の配列 */ int[][] scc() { start = new int[n + 1]; for (Edge e : edges) { start[e.from + 1]++; } for (int i = 1; i <= n; i++) { start[i] += start[i - 1]; } elist = new Edge[edges.size()]; int[] counter = Arrays.copyOf(start, n + 1); for (Edge e : edges) { elist[counter[e.from]++] = e; } nowOrd = 0; groupNum = 0; visited = new ArrayDeque<>(); low = new int[n]; ord = new int[n]; gid = new int[n]; Arrays.fill(ord, -1); for (int i = 0; i < n; i++) { if (ord[i] == -1) { dfs(i); } } for (int i = 0; i < n; i++) { gid[i] = groupNum - 1 - gid[i]; } int[] counts = new int[groupNum]; for (int x : gid) { counts[x]++; } int[][] groups = new int[groupNum][]; for (int i = 0; i < groupNum; i++) { groups[i] = new int[counts[i]]; } for (int i = 0; i < n; i++) { int idx = gid[i]; groups[idx][--counts[idx]] = i; } return groups; } private void dfs(int v) { low[v] = ord[v] = nowOrd++; visited.add(v); for (int i = start[v]; i < start[v + 1]; i++) { int to = elist[i].to; if (ord[to] == -1) { dfs(to); low[v] = Math.min(low[v], low[to]); } else { low[v] = Math.min(low[v], ord[to]); } } if (low[v] == ord[v]) { while (true) { int u = visited.pollLast(); ord[u] = n; gid[u] = groupNum; if (u == v) { break; } } groupNum++; } } } class DSU { private int n; private int[] parentOrSize; private int num; /** * n頂点0辺の無向グラフを作る。
* O(n) * * @param n 頂点数 */ public DSU(int n) { this.n = n; this.parentOrSize = new int[n]; Arrays.fill(parentOrSize, -1); num = n; } /** * 辺(a, b)を足す。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @param b 頂点番号(0≦b<n) * @return 代表元 */ int merge(int a, int b) { assert 0 <= a && a < n : "a=" + a; assert 0 <= b && b < n : "b=" + b; int x = leader(a); int y = leader(b); if (x == y) { return x; } if (-parentOrSize[x] < -parentOrSize[y]) { int tmp = x; x = y; y = tmp; } parentOrSize[x] += parentOrSize[y]; parentOrSize[y] = x; num--; return x; } /** * 頂点a, bが連結かどうか。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @param b 頂点番号(0≦b<n) * @return true:連結 false:非連結 */ boolean same(int a, int b) { assert 0 <= a && a < n : "a=" + a; assert 0 <= b && b < n : "b=" + b; return leader(a) == leader(b); } /** * 頂点aの属する連結成分の代表元を返す。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @return 代表元 */ int leader(int a) { assert 0 <= a && a < n : "a=" + a; if (parentOrSize[a] < 0) { return a; } else { return parentOrSize[a] = leader(parentOrSize[a]); } } /** * 頂点aの属する連結成分の要素数を返す。
* ならしO(α(n)) * * @param a 頂点番号(0≦a<n) * @return 要素数 */ int size(int a) { assert 0 <= a && a < n : "a=" + a; return -parentOrSize[leader(a)]; } /** * 連結成分の数を返す。
* O(1) * * @return 連結成分数 */ int num() { return num; } /** * グラフを連結成分に分けた情報を返す。
* O(n) * * @return 「1つの連結成分の頂点番号のリスト」のリスト */ List> groups() { int[] leaderBuf = new int[n]; int[] groupSize = new int[n]; for (int i = 0; i < n; i++) { leaderBuf[i] = leader(i); groupSize[leaderBuf[i]]++; } List> result = new ArrayList<>(n); for (int i = 0; i < n; i++) { result.add(new ArrayList<>(groupSize[i])); } for (int i = 0; i < n; i++) { result.get(leaderBuf[i]).add(i); } result.removeIf(List::isEmpty); return result; } }