Longest paths P54384

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⁴ and 0 ≤ m ≤ 5n.

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.