Per gestire meglio il pascolo, Farmer John ha installato sentieri a senso unico. La fattoria ha $N$ campi numerati $1..N$ e ogni sentiero ne collega due. Da $X$ a $Y$ permette di andare da $X$ a $Y$, ma non viceversa.

Bessie ama mangiare in più campi possibile. Parte ogni mattina dal $1$, visita una sequenza e torna al $1$. Massimizza i campi distinti: mangia l’erba di ciascuno una sola volta anche se lo visita più volte.

Il senso unico non le piace, perché riduce le visite. Quanto mangerà violando la regola su al massimo un sentiero? Calcola il massimo di campi distinti in un percorso che parte e termina al $1$, con al massimo un passaggio contromano. Può andare contromano una sola volta nell’intero viaggio, nemmeno sullo stesso sentiero due volte.

Input

La prima riga contiene il numero di campi $N$ e sentieri $M$ ($1 \leq N, M \leq 100,000$).

Le successive $M$ righe danno due numeri distinti $X$, $Y$ per un sentiero da $X$ a $Y$. Nessun sentiero si ripete.

Output

Stampa in una riga il massimo di campi distinti in un percorso dal $1$ al $1$ con al massimo un passaggio contromano.

Esempi

Input 1

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

Output 1

6

Note

Disegno ASCII dell’esempio:

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

Può visitare $1,2,4,7,2,5,3,1$ andando contromano sul sentiero tra $5$ e $3$. Al $3$ non può raggiungere $6$ senza un altro passaggio contromano.

Autore del problema: Mark Gordon, 2015