Distinct Routes

warning: unused imports: `Reverse`, `max`, `min`
 --> input/code.rs:1:16
  |
1 | use std::cmp::{max, min, Reverse};
  |                ^^^  ^^^  ^^^^^^^
  |
  = note: `#[warn(unused_imports)]` on by default

warning: unused imports: `BinaryHeap`, `HashMap`, `HashSet`
 --> input/code.rs:2:24
  |
2 | use std::collections::{BinaryHeap, HashMap, HashSet};
  |                        ^^^^^^^^^^  ^^^^^^^  ^^^^^^^

warning: unused import: `std::process::exit`
 --> input/code.rs:4:5
  |
4 | use std::process::exit;
  |     ^^^^^^^^^^^^^^^^^^

warning: 3 warnings emitted

use std::cmp::{max, min, Reverse};
use std::collections::{BinaryHeap, HashMap, HashSet};
use std::io::{self, Read};
use std::process::exit;

macro_rules! input {
    ($it: expr) => {
        $it.next().unwrap().parse().unwrap()
    };
    ($it: expr, $T: ty) => {
        $it.next().unwrap().parse::<$T>().unwrap()
    };
}
/*
mod classes;
mod homework;

fn main() {
    // println!("{}", "-".repeat(20));
    classes::c14::task2();
    // homework::hw5::task2();
    // println!("{}", "-".repeat(20));
}
// */

fn dfs(g: &mut Vec<Vec<usize>>, n: usize, i: usize, t: usize, visited: &mut Vec<bool>, path: &mut Vec<usize>) -> bool {
    if i==t {
        path.push(i);
        return true
    }
    visited[i] = true;
    let mut found = false;

    for j in 0..n {
        if g[i][j]>0 {
            if !visited[j] {
                found = dfs(g, n, j, t, visited, path);
            }
            if found {
                path.push(i);
                g[i][j] = 0;
                return true;
            }
        }
    }
    false
}


fn main() {
    let mut buf = String::new();
    io::stdin().read_to_string(&mut buf).unwrap();

    let mut it = buf.split_whitespace();

    let (n, mut m): (usize, usize) = (input!(it), input!(it));

    let mut g: Vec<Vec<usize>> = vec![vec![0; n]; n];

    while m>0 {
        let (u, v): (usize, usize) = (input!(it), input!(it));
        g[u-1][v-1]=1;
        m-=1;
    }

    let mut paths: Vec<Vec<usize>> = vec![];
    paths.push(vec![]);

    let mut exists_path = true;

    let mut n_paths = 0;

    while exists_path {
        let mut visited = vec![false; n];
        exists_path = dfs(&mut g, n, 0, n-1, &mut visited, &mut paths[n_paths]);
        if exists_path {
            paths.push(vec![]);
            n_paths+=1;
        }
    }

    println!("{}", n_paths);

    for v in paths {
        if !v.is_empty() {
            println!("{}", v.len());
            for x in v.iter().rev() {
                print!("{} ", x + 1);
            }
            println!();
        }
    }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: WRONG ANSWER

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: WRONG ANSWER

Test 15

Verdict: WRONG ANSWER