#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include // #pragma GCC target("avx") // #pragma GCC optimize("O3") // #pragma GCC optimize("unroll-loops") // string abc = "abcdefghijklmnopqrstuvwxyz"; // string abc = "ABCDEFGHIJKLMNOPQRSTUVWXYZ"; using namespace std; using namespace atcoder; using ll = long long; using ld = long double; using ull = unsigned long long; using mint = modint998244353; //using mint = modint1000000007; template using pq = priority_queue;//降順?(最大取り出し) template using pqg = priority_queue, greater>;//昇順?(最小取り出し) template using vector2 = vector>; template using vector3 = vector>>; template using vector4 = vector>>>; template using vector5 = vector>>>>; template using vector6 = vector>>>>>; template using pairs = pair; #define rep(i, n) for (ll i = 0; i < ll(n); i++) #define rep1(i,n) for(int i = 1;i <= int(n);i++) #define repm(i, m, n) for (int i = (m); (i) < int(n);(i)++) #define repmr(i, m, n) for (int i = (m) - 1; (i) >= int(n);(i)--) #define rep0(i,n) for(int i = n - 1;i >= 0;i--) #define rep01(i,n) for(int i = n;i >= 1;i--) /// ここから//////////////////////////////////////////// int main() { int n; cin >> n; scc_graph g(n);//AtCoder Libraryのsccを使用 vector2 b(n,vector(0));//チェック2にて使用する入力をそのまま管理する配列/vector2はvector>を表します(34行目にて定義) for(int j = 0;j < n; j++){ int m; cin >> m; for(int i = 0;i < m;i++){ int a; cin >> a; a--; b[j].push_back(a); g.add_edge(j,a); } } vector> sorted = g.scc();//強連結成分分解からのトポロジカルソート(AtCoder Libraryの機能) vector topol(n);//その頂点(人)が何番目の強連結成分に存在するかを保存 rep(j,sorted.size()){ for(int i : sorted[j]){ topol[i] = j; } } bool ans = 0;//二つのチェックを通ったらYes for(int j : sorted[0]){//チェック1:頂点(人)1がトポロジカルソートされた強連結成分たちのうち先頭に位置しているか if(j == 0){ ans = 1; } } rep(j,sorted.size()-1){//チェック2:トポロジカルソートされた強連結成分たちについてある強連結成分から次の強連結成分へ移動可能か bool c = 0; for(int i : sorted[j]){ for(int k : b[i]){ if(topol[k] == j+1)c = 1; } } if(!c)ans = 0;//次の強連結成分へ移動できないなら答えはNo } if(ans)cout << "Yes" << endl; else cout << "No" << endl; return 0; }