Der Kuhboom verstopft Wege zur Scheune. Farmer John untersucht Engpässe, um „Staus“ beim Melken zu lindern.

$M$ ($1 \le M \le 50,000$) Einbahnwege verbinden zwei verschiedene aus $N$ ($1 \le N \le 5,000$) Kreuzungen $1..N$, Scheune bei $N$. Immer zu größerer Nummer, daher keine Zyklen, alle führen zur Scheune. Mehrere Wege je Punktpaar möglich.

Zur Melk-Rushhour starten Kühe an ihren Weidepunkten: genau Kreuzungen ohne eingehende Wege. Ein „Pfad“ ist Wegfolge vom Weidepunkt zur Scheune.

Finde maximale Zahl möglicher Pfade mit einem gegebenen Weg für den verkehrsreichsten. Antwort passt in vorzeichenbehaftete 32-Bit-Ganzzahl.

Eingabe

Zeile 1: ganze $N$, $M$ mit Leerzeichen.

Zeilen $2..M+1$: zwei Kreuzungen mit Leerzeichen.

Ausgabe

Zeile 1: maximale Pfadzahl über einen Weg.

Beispiele

Eingabe 1

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

Ausgabe 1

4

Hinweis

Vier mögliche Pfade zur Scheune:

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

Quelle: USACO März 2007.