use std::io::*; fn mul(a: &Vec>, b: &Vec>) -> Vec> { let n = a.len(); let m = b[0].len(); let mut c = vec![vec![false; m]; n]; for k in 0..n { for i in 0..n { for j in 0..m { c[i][j] |= a[i][k] & b[k][j]; } } } c } fn main() { let mut s: String = String::new(); std::io::stdin().read_to_string(&mut s).ok(); let mut itr = s.trim().split_whitespace(); let n: usize = itr.next().unwrap().parse().unwrap(); let m: usize = itr.next().unwrap().parse().unwrap(); let mut t: usize = itr.next().unwrap().parse().unwrap(); let mut a = vec![vec![false; n]; n]; let mut res = vec![vec![true; n]; n]; for _ in 0..m { let u: usize = itr.next().unwrap().parse().unwrap(); let v: usize = itr.next().unwrap().parse().unwrap(); a[u][v] = true; } while t > 0 { if t & 1 == 1 { res = mul(&res, &a); } a = mul(&a, &a); t >>= 1; } let from = vec![vec![true; 1]; n]; let to = mul(&res, &from); let mut ans = 0; for i in 0..n { if to[i][0] { ans += 1; } } println!("{}", ans); }