/* #pragma GCC optimize("Ofast,unroll-loops") #pragma GCC target("avx2,fma,bmi,bmi2,sse4.2,popcnt,lzcnt") */ #include #define taskname "" #define all(x) x.begin(), x.end() #define rall(x) x.rbegin(), x.rend() #define i64 long long #define pb push_back #define ff first #define ss second #define isz(x) (int)x.size() using namespace std; const int mxN = 2e5 + 5; const int mod = 1e9 + 7; const i64 oo = 1e18; template struct graph{ using Weight_t = T; struct Edge_t{ int from, to; T cost; }; int n; vector edge; vector> adj; function ignore; graph(int n = 1): n(n), adj(n){ assert(n >= 1); } graph(const vector> &adj, bool undirected = true): n((int)adj.size()), adj(n){ assert(n >= 1); if(undirected){ for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) if(u < v) link(u, v); } else for(auto u = 0; u < n; ++ u) for(auto v: adj[u]) orient(u, v); } graph(const vector>> &adj, bool undirected = true): n((int)adj.size()), adj(n){ assert(n >= 1); if(undirected){ for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) if(u < v) link(u, v, w); } else for(auto u = 0; u < n; ++ u) for(auto [v, w]: adj[u]) orient(u, v, w); } graph(int n, vector> &edge, bool undirected = true): n(n), adj(n){ assert(n >= 1); for(auto [u, v]: edge) undirected ? link(u, v) : orient(u, v); } graph(int n, vector> &edge, bool undirected = true): n(n), adj(n){ assert(n >= 1); for(auto [u, v, w]: edge) undirected ? link(u, v, w) : orient(u, v, w); } int add_vertex(){ adj.emplace_back(); return n ++; } int operator()(int u, int id) const{ #ifdef LOCAL assert(0 <= id && id < (int)edge.size()); assert(edge[id].from == u || edge[id].to == u); #endif return u ^ edge[id].from ^ edge[id].to; } int link(int u, int v, T w = {}){ // insert an undirected edge int id = (int)edge.size(); adj[u].push_back(id), adj[v].push_back(id), edge.push_back({u, v, w}); return id; } int orient(int u, int v, T w = {}){ // insert a directed edge int id = (int)edge.size(); adj[u].push_back(id), edge.push_back({u, v, w}); return id; } vector neighbor(int u, int exclude = -1) const{ vector res; for(auto id: adj[u]){ if(id == exclude || ignore && ignore(id)) continue; res.push_back(operator()(u, id)); } return res; } void clear(){ for(auto [u, v, w]: edge){ adj[u].clear(); adj[v].clear(); } edge.clear(); ignore = {}; } graph transpose() const{ // the transpose of the directed graph graph res(n); for(auto id = 0; id < (int)edge.size(); ++ id){ if(ignore && ignore(id)) continue; res.orient(edge[id].to, edge[id].from, edge[id].cost); } return res; } int degree(int u) const{ // the degree (outdegree if directed) of u (without the ignoration rule) return (int)adj[u].size(); } // The adjacency list is sorted for each vertex. vector> get_adjacency_list() const{ vector> res(n); for(auto u = 0; u < n; ++ u) for(auto id: adj[u]){ if(ignore && ignore(id)) continue; res[(*this)(u, id)].push_back(u); } return res; } void set_ignoration_rule(const function &f){ ignore = f; } void reset_ignoration_rule(){ ignore = nullptr; } friend ostream &operator<<(ostream &out, const graph &g){ for(auto id = 0; id < (int)g.edge.size(); ++ id){ if(g.ignore && g.ignore(id)) continue; auto &e = g.edge[id]; out << "{" << e.from << ", " << e.to << ", " << e.cost << "}\n"; } return out; } }; // Requires graph struct strongly_connected_components{ int n, attempt; vector dp; vector stack; vector assigned; vector was; // condensation descriptions vector belongs; // vertex -> component vector> comp; // in topological order graph condensation; // edge weights are the original edge id // strongly_connectsed_components(){ } strongly_connected_components(int n){ init(n); } template strongly_connected_components(const graph &g){ init(g.n); run_all(g); } void init(int n){ this->n = n; dp.assign(n, -1); stack.reserve(n); assigned.assign(n, -1); was.assign(n, -2); attempt = -1; belongs.assign(n, -1); comp.clear(); } // O(n + m) where n and m are the number of reachable nodes and edges respectively. template void _run(const graph &g, const vector &src){ int it = 0; auto dfs = [&](auto self, int u)->int{ int low = dp[u] = ++ it; was[u] = attempt; stack.push_back(u); for(auto id: g.adj[u]){ if(g.ignore && g.ignore(id)) continue; int v = g.edge[id].to; if(assigned[v] != attempt){ if(was[v] != attempt){ was[v] = attempt; dp[v] = -1; } low = min(low, ~dp[v] ? dp[v] : self(self, v)); } } if(low == dp[u]){ vector c; while(true){ int v = stack.back(); stack.pop_back(); assigned[v] = attempt; c.push_back(v); if(u == v) break; } comp.push_back(move(c)); } return dp[u] = low; }; for(auto u: src) if(was[u] != attempt) dfs(dfs, u); reverse(comp.begin(), comp.end()); condensation = {count()}; for(auto i = 0; i < count(); ++ i) for(auto u: comp[i]) belongs[u] = i; for(auto i = 0; i < count(); ++ i) for(auto u: comp[i]) for(auto id: g.adj[u]){ if(g.ignore && g.ignore(id)) continue; int v = g(u, id); if(i != belongs[v]){ assert(i < belongs[v]); condensation.orient(i, belongs[v], id); } } } template void run(const graph &g, const vector &src){ assert(g.n <= n); for(auto u: src) assert(0 <= u && u < g.n); comp.clear(); ++ attempt; _run(g, src); } template void run_all(const graph &g){ assert(g.n <= n); comp.clear(); ++ attempt; vector src(n); iota(src.begin(), src.end(), 0); _run(g, src); } // Check if u is visited during the last run-like call bool visited(int u) const{ assert(0 <= u && u < n); return was[u] == attempt; } // # of strongly connected components int count() const{ return (int)comp.size(); } }; void solve() { int n; cin >> n; graph g(n); for (int i = 0; i < n; ++i) { int cnt; cin >> cnt; while (cnt--) { int val; cin >> val; g.orient(i, --val); } } strongly_connected_components scc(g); int cnt = scc.count(); bool res = true; g = scc.condensation; auto dfs = [&](auto self, int v) -> void { --cnt; if (g.degree(v) == 0) return; set s; for (auto id : g.adj[v]) s.insert(g(v, id)); if (isz(s) > 1) { res = false; return; } self(self, g(v, g.adj[v][0])); }; dfs(dfs, scc.belongs[0]); res &= (cnt == 0); cout << (res ? "Yes" : "No") << endl; } signed main() { #ifndef CDuongg if(fopen(taskname".inp", "r")) assert(freopen(taskname".inp", "r", stdin)), assert(freopen(taskname".out", "w", stdout)); #else freopen("bai3.inp", "r", stdin); freopen("bai3.out", "w", stdout); auto start = chrono::high_resolution_clock::now(); #endif ios_base::sync_with_stdio(false); cin.tie(nullptr); int t = 1; //cin >> t; while(t--) solve(); #ifdef CDuongg auto end = chrono::high_resolution_clock::now(); cout << "\n"; for(int i = 1; i <= 100; ++i) cout << '='; cout << "\nExecution time: " << chrono::duration_cast (end - start).count() << "[ms]" << endl; cout << "Check array size pls sir" << endl; #endif }