Aby lepiej zarządzać wypasem, Farmer John zbudował jednokierunkowe ścieżki. Farma ma $N$ pól numerowanych $1..N$, a ścieżka łączy dwa pola. Ścieżka z $X$ do $Y$ pozwala iść z $X$ do $Y$, lecz nie odwrotnie.

Bessie lubi jeść trawę na jak największej liczbie pól. Zaczyna rano w polu $1$, odwiedza ciąg pól i wraca do $1$. Maksymalizuje różne pola, gdyż trawę na wielokrotnie odwiedzonym polu je tylko raz.

Nie lubi jednokierunkowości, bo ogranicza wizyty. Ile zje, łamiąc zasady na najwyżej jednej ścieżce? Wyznacz największą liczbę różnych pól na trasie z $1$ do $1$ z najwyżej jednym przejściem pod prąd. W całej podróży wolno to zrobić tylko raz, nawet tę samą ścieżkę nie można przejść pod prąd dwa razy.

Wejście

Pierwszy wiersz zawiera liczbę pól $N$ i ścieżek $M$ ($1 \leq N, M \leq 100,000$).

Kolejne $M$ wierszy podaje różne numery $X$, $Y$ dla ścieżki z $X$ do $Y$. Ścieżki się nie powtarzają.

Wyjście

Wypisz w jednym wierszu największą liczbę różnych pól trasy z $1$ do $1$ z najwyżej jednym przejściem pod prąd.

Przykład

Wejście 1

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

Wyjście 1

6

Uwagi

Rysunek ASCII przykładu:

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

Może odwiedzić $1,2,4,7,2,5,3,1$, przechodząc pod prąd między $5$ i $3$. Z $3$ nie może dotrzeć do $6$ bez kolejnego przejścia pod prąd.

Autor zadania: Mark Gordon, 2015