Longest paths P54384


Statement
 

pdf   zip

thehtml

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