Um das Grasen besser zu steuern, hat Farmer John überall Einbahnwege angelegt. Die Farm hat $N$ Felder mit Nummern $1..N$, und jeder Weg verbindet zwei Felder. Ein Weg von $X$ nach $Y$ erlaubt die Fahrt von $X$ nach $Y$, aber nicht zurück.

Bessie frisst gern Gras auf möglichst vielen Feldern. Sie startet morgens in Feld $1$, besucht eine Folge von Feldern und kehrt abends zu $1$ zurück. Sie maximiert die Zahl verschiedener Felder, da sie bei mehrfachen Besuchen nur einmal dort frisst.

Die Einbahnregel gefällt ihr nicht, weil sie weniger Felder erreichen kann. Wie viel Gras kann sie fressen, wenn sie höchstens einen Weg entgegen der Richtung benutzt? Bestimme die größte Zahl verschiedener Felder auf einer Route von $1$ zurück zu $1$ mit höchstens einer Fahrt gegen die Richtung. Das ist insgesamt nur einmal erlaubt; selbst derselbe Weg darf nicht zweimal rückwärts befahren werden.

Eingabe

Die erste Zeile enthält Feldzahl $N$ und Wegzahl $M$ ($1 \leq N, M \leq 100,000$).

Die nächsten $M$ Zeilen geben verschiedene Feldnummern $X$, $Y$ für einen Weg von $X$ nach $Y$. Kein Weg kommt mehrfach vor.

Ausgabe

Gib in einer Zeile die größte Zahl verschiedener Felder einer Route von $1$ nach $1$ mit höchstens einer Fahrt gegen die Richtung aus.

Beispiele

Eingabe 1

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

Ausgabe 1

6

Hinweis

ASCII-Zeichnung des Beispiels:

v---3-->6
7   |\  |
^\  v \ |
| \ 1  \|
|  \|   v
|   v   5
4<--2---^

Sie kann $1,2,4,7,2,5,3,1$ besuchen, indem sie den Weg zwischen $5$ und $3$ rückwärts benutzt. In $3$ kann sie $6$ nicht ohne einen weiteren Rückwärtsweg erreichen.

Aufgabenautor: Mark Gordon, 2015