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 10^{4}),
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++