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 10*n*),
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 5 7 1 0 1 3 1 4 2 3 2 4 0 1 0 2

**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

Information

- Author
- Salvador Roura
- Language
- English
- Translator
- Salvador Roura
- Original language
- Catalan
- Other languages
- Catalan
- Official solutions
- C++
- User solutions
- C++