// I plan to use an unusual approach to this problem: it is not based on
// graph traversals but on transformations of directed graphs under which
// the number of paths bettween the start and end is invariant.
#![feature(hash_drain_filter)]

use std::collections::BTreeSet;
use std::collections::VecDeque;

    let mut graph = build_graph(&mut parse_edges(

    let graph = build_graph(&mut parse_edges(

    trim_graph(&mut graph);

    println!("{} paths", count_paths(&graph));
}
fn count_paths(graph: &HashMap<usize, HashMap<usize, u128>>) -> u128 {
    let mut q: VecDeque<(usize, BTreeSet<usize>)> = once((0, BTreeSet::new())).collect();
    let mut r: HashMap<usize, HashMap<BTreeSet<usize>, u128>> = once((0, once((BTreeSet::new(), 1)).collect())).collect();
    while let Some((n, p)) = q.pop_front() {
        match (r.get(&n).and_then(|s| s.get(&p)), graph.get(&n)) {
            (Some(c), Some(e)) => {
                let c = *c;
                let mut next_p = p.clone();
                next_p.insert(n);
                for (t, w) in e.iter().filter(|(t,_)| !p.contains(t)) {
                    let d = c * *w;
                    r.entry(*t).or_insert_with(|| HashMap::new()).entry(next_p.clone()).and_modify(|g| *g += d).or_insert(d);
                    q.push_back((*t, next_p.clone()));
                }
            }
            _ => {}
        }
    }
    r.get(&1).map(|z| z.iter().map(|(_,n)| *n).sum()).unwrap_or(0)

fn trim_graph(graph: &mut HashMap<usize, HashMap<usize, u128>>) -> bool {
    use std::collections::HashSet;
    let mut ever_changed = false;
    loop {
        let mut changed = false;
        let reachable: HashSet<_> = graph
            .values()
            .flat_map(|e| e.keys())
            .copied()
            .chain(once(0))
            .collect();
        let reached: HashSet<_> = graph.keys().copied().collect();
        graph
            .drain_filter(|s, e| {
                e.drain_filter(|t, n| {
                    if *n == 0 || !reached.contains(t) {
                        changed = true;
                        true
                    } else {
                        false
                    }
                })
                .for_each(drop);
                if *s > 1 && (!reachable.contains(s) || e.is_empty()) {
                    changed = true;
                    true
                } else {
                    false
                }
            })
            .for_each(drop);
        if changed {
            ever_changed = true;
        } else {
            break;
        }
    }
    ever_changed
}