#![allow(unused_imports)] fn main() { input! { n: usize, e: usize, f: Usize1, t: Usize1, e: [(Usize1, Usize1); e], } let mut g = vec![BTreeSet::new(); n]; for (a, b) in e { g[a].insert(b); g[b].insert(a); } let mut loope = BTreeSet::new(); { let mut g = g.clone(); let mut que = VecDeque::new(); for (v, g) in g.iter().enumerate() { if g.len() == 1 { que.push_back(v); } } while let Some(v) = que.pop_front() { let e = g[v].clone(); for u in e { g[u].remove(&v); g[v].remove(&u); if g[u].len() == 1 { que.push_back(u); } } } for (v, g) in g.into_iter().enumerate() { for u in g { loope.insert((v, u)); } } } // eprintln!("{loope:?}"); let mut que = VecDeque::new(); let mut dp = vec![(usize::MAX, 0); n]; que.push_back(f); dp[f] = (0, 0); while let Some(v) = que.pop_front() { for &u in &g[v] { match dp[u].0.cmp(&(dp[v].0 + 1)) { std::cmp::Ordering::Less => { } std::cmp::Ordering::Equal => { chmax!(dp[u].1, dp[v].1 + if loope.contains(&(v, u)) { 1 } else { 0 }); } std::cmp::Ordering::Greater => { dp[u] = dp[v]; dp[u].0 += 1; if loope.contains(&(v, u)) { dp[u].1 += 1; } que.push_back(u); } } } } if dp[t].0 == usize::MAX { println!("-1"); } else { println!("{}", dp[t].1); } } use proconio::{input, marker::*}; use itertools::{iproduct, izip, Itertools as _}; use std::{cmp::Reverse, collections::*}; #[macro_export] macro_rules! chmax { ($a:expr, $b:expr) => {{ let tmp = $b; if $a < tmp { $a = tmp; true } else { false } }}; } #[macro_export] macro_rules! chmin { ($a:expr, $b:expr) => {{ let tmp = $b; if $a > tmp { $a = tmp; true } else { false } }}; } #[macro_export] /// mvec![] macro_rules! mvec { ($val:expr; ()) => { $val }; ($val:expr; ($size:expr $(,$rest:expr)*)) => { vec![mvec![$val; ($($rest),*)]; $size] }; }