Write a program such that, given a directed graph without cycles, computes the number of vertices of the longest path in the graph, and the number of paths with this length.

**Input**

Input consists of several cases.
Every case begins with the number of vertices *n* and the number of edges *m*.
Follow *m* pairs *x* *y* indicating that there is an arc from *x* to *y*.
There are no repeated arcs.
Vertices are numbered starting at 0.
Assume 1 ≤ *n* ≤ 10^{4} and 0 ≤ *m* ≤ 5*n*.

**Output**

For every case, print two numbers: the length of the longest path, and how many paths have this length. The test cases are such that both values fit into an integer number.

Public test cases

**Input**

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

**Output**

3 1 1 5 4 4

Information

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