Number of shortest paths P77353


Statement
 

pdf   zip

thehtml

Given a directed graph, compute in how many ways every vertex is reachable from the vertex 0 making the minim number of steps.

Input

Input consists of several cases, each one with the number of vertices n (between 1 and 104), the number of arcs m (between 0 and 10n), and m pairs x ⁠ ⁠ y to indicate an arc from x to ‍y. There are no repeated arcs, nor of the kind x ⁠ ⁠ x. Vertices are numbered from 0 to n − 1.

Output

For every case, and for every vertex x, print its number, the minimum number of steps to reach x starting from 0, and in how many different ways this can be done. Print a -1 if a vertex is unreachable from 0. Print an empty line after every case.

Public test cases
  • Input

    4 3
         0 1
         1 2
         2 3
    
    2 0
    
    8 15
         0 1
         0 2
         1 3
         1 4
         2 3 
         2 4
         3 5
         3 6
         4 5
         4 6
         5 7
         5 1
         6 7
         6 2
         1 0
    
    
    

    Output

    0: 0 1
    1: 1 1
    2: 2 1
    3: 3 1
    
    0: 0 1
    1: -1
    
    0: 0 1
    1: 1 1
    2: 1 1
    3: 2 2
    4: 2 2
    5: 3 4
    6: 3 4
    7: 4 8
    
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Translator
    Salvador Roura
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python