L'explosion du nombre de vaches congestionne les chemins vers la grange. Farmer John étudie les goulets pour réduire les « bouchons » à la traite.

$M$ ($1 \le M \le 50,000$) chemins à sens unique relient deux points différents parmi $N$ ($1 \le N \le 5,000$) intersections $1..N$, grange en $N$. Vers numéro supérieur, donc aucun cycle, tous mènent à la grange. Plusieurs chemins par paire sont possibles.

À l'heure de pointe, les vaches partent de leurs pâturages vers la grange : exactement les intersections sans chemin entrant. Un « parcours » est une suite de chemins de là à la grange.

Trouvez le maximum de parcours possibles contenant un seul chemin donné, pour le plus fréquenté. Réponse dans un entier signé 32 bits.

Entrée

Ligne 1 : entiers $N$, $M$ séparés par un espace.

Lignes $2..M+1$ : deux intersections séparées par un espace.

Sortie

Ligne 1 : maximum de parcours traversant un chemin.

Exemples

Entrée 1

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

Sortie 1

4

Remarque

Quatre parcours possibles vers la grange :

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

Source : USACO mars 2007.