Wzrost liczby krów zatyka ścieżki do stodoły. Farmer John bada wąskie gardła, by zmniejszyć „korki” przy dojeniu.

$M$ ($1 \le M \le 50,000$) jednokierunkowych ścieżek łączy różne pary $N$ ($1 \le N \le 5,000$) skrzyżowań $1..N$, stodoła w $N$. Zawsze do większego numeru, bez cykli, wszystkie do stodoły. Możliwe liczne ścieżki między parą.

W szczycie krowy idą z pastwisk do stodoły: to dokładnie punkty bez wejściowych ścieżek. „Droga” to ciąg ścieżek z takiego punktu do stodoły.

Znajdź maksymalną liczbę możliwych dróg zawierających jedną wybraną ścieżkę dla najbardziej obciążonej. Odpowiedź mieści się w całkowitej ze znakiem 32 bitów.

Wejście

Wiersz 1: całkowite $N$, $M$ ze spacją.

Wiersze $2..M+1$: dwa skrzyżowania ze spacją.

Wyjście

Wiersz 1: maksimum dróg przez jedną ścieżkę.

Przykład

Wejście 1

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

Wyjście 1

4

Uwagi

Cztery możliwe drogi do stodoły:

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

Źródło: USACO marzec 2007.