El aumento de vacas congestiona caminos al establo. Farmer John estudia cuellos de botella para reducir «atascos» al ordeñar.

$M$ ($1 \le M \le 50,000$) caminos unidireccionales unen dos puntos distintos de $N$ ($1 \le N \le 5,000$) cruces $1..N$, establo en $N$. Van a número mayor, sin ciclos, todos al establo. Puede haber varios por par.

En hora punta salen de lugares de pastoreo al establo: exactamente cruces sin caminos entrantes. «Ruta» es secuencia de caminos desde allí al establo.

Halla máximo de rutas posibles que contienen un camino dado, para hallar el más ocupado. Respuesta cabe en entero con signo de 32 bits.

Entrada

Línea 1: enteros $N$, $M$ con espacios.

Líneas $2..M+1$: dos cruces con espacios.

Salida

Línea 1: máximo rutas por un camino.

Ejemplos

Entrada 1

7 7
1 3
3 4
3 5
4 6
2 3
5 6
6 7

Salida 1

4

Nota

Cuatro rutas posibles al establo:

1 3 4 6 7
1 3 5 6 7
2 3 4 6 7
2 3 5 6 7

Fuente: USACO marzo 2007.