use std::collections::VecDeque; use proconio::{input, marker::Usize1}; fn main() { input! { n:usize, a:[[Usize1];n], } let mut g = vec![vec![]; n]; let mut rg = vec![vec![]; n]; for i in 0..n { for &j in a[i].iter() { g[i].push(j); rg[j].push(i); } } let mut ord = vec![]; let mut vis = vec![false; n]; for i in 0..n { if vis[i] { continue; } dfs(i, &g, &mut vis, &mut ord); } ord.reverse(); for i in 0..n { vis[i] = false; } let mut groups = vec![]; let mut newvs = vec![0; n]; let mut newv = 0; for &v in ord.iter() { if vis[v] { continue; } let mut group = vec![]; dfs1(v, &rg, &mut vis, &mut group); for &u in group.iter() { newvs[u] = newv; } newv += 1; groups.push(group); } let newn = groups.len(); let mut newg = vec![vec![]; newn]; let mut newrg = vec![vec![]; newn]; let mut indegs = vec![0; newn]; for i in 0..n { for &j in a[i].iter() { if newvs[i] == newvs[j] { continue; } newg[newvs[i]].push(newvs[j]); newrg[newvs[j]].push(newvs[i]); indegs[newvs[j]] += 1; } } let mut q = VecDeque::new(); for i in 0..newn { if indegs[i] == 0 { q.push_back(i); } } let mut topo = vec![]; while let Some(crr) = q.pop_front() { topo.push(crr); for &nxt in newg[crr].iter() { if indegs[nxt] == 0 { continue; } indegs[nxt] -= 1; if indegs[nxt] == 0 { q.push_back(nxt); } } } topo.reverse(); let mut dp = vec![0; newn]; for i in 0..newn { for &j in newrg[topo[i]].iter() { dp[j] = dp[j].max(dp[topo[i]] + 1); } } let ans = dp[newvs[0]] + 1 == newn; println!("{}", if ans { "Yes" } else { "No" }); } fn dfs(crr: usize, g: &Vec>, vis: &mut Vec, ord: &mut Vec) { vis[crr] = true; for &nxt in g[crr].iter() { if vis[nxt] { continue; } dfs(nxt, g, vis, ord); } ord.push(crr); } fn dfs1(crr: usize, g: &Vec>, vis: &mut Vec, group: &mut Vec) { vis[crr] = true; group.push(crr); for &nxt in g[crr].iter() { if vis[nxt] { continue; } dfs1(nxt, g, vis, group); } }