Because of necessary software maintenance, Jutge.org may not fully work on the 7 of may, from 8 to 10 CEST.

Longest paths P54384

Statement

html

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.

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