Camins més llargs P54384

Statement

Feu un programa que, donat un graf dirigit sense cicles, calculi el nombre de vèrtexs del camí més llarg del graf. A més, cal calcular quants camins tenen aquesta longitud.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs $n$ i el nombre d’arestes $m$ . Segueixen $m$ parells $x \enspace y$ indicant que hi ha un arc de $x$ a $y$ . No hi ha arcs repetits. Els vèrtexs es numeren començant en 0. Suposeu $1 \le n \le 10^4$ i $0 \le m \le 5n$ .

Sortida

Per a cada cas, escriviu dos nombres: la longitud del camí més llarg, i quants camins tenen aquesta longitud. Els jocs de proves són tals que els dos nombres caben en un enter.

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: Catalan
Other languages: English
Official solutions: C++
User solutions: C++