# Number of shortest paths P77353

Statement

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