En un esfuerzo para manejar mejor los patrones de pasteo de sus vacas, el Granjero Juan ha instalado caminos de un sentido en su granja. La granja consiste de ~N~ campos, convenientemente numerados ~1..N~, en los cuales cada camino de un sentido conecta un par de campos. Por ejemplo, si un camino conecta el campo ~X~ con el campo ~Y~, entonces las vacas pueden ir de ~X~ a ~Y~ pero no de ~Y~ a ~X~.

Bessie la vaca, como todos sabemos, disfruta comiendo pasto de tantos campos como sea posible. Ella siempre comienza en el campo ~1~ al comienzo del día y visita una sucesión de campos, volviendo al campo ~1~ al final del día. Ella intenta maximizar el número de distintos campos en su ruta, desde que ella consigue comer el pasto en cada uno (si ella visita un campo varias veces, ella únicamente come el campo allí una vez).

Como uno puede imaginar, Bessie no está particularmente contenta con la restricción de un solo sentido en los caminos de GJ, pues esto reducirá probablemente el número de campos distintos que ella pueda visitar posiblemente en su ruta diaria. Ella se pregunta cuánto pasto ella será capaz de comer si ella rompe la las reglas y recorre un camino en la dirección incorrecta.

Por favor, calcule el número máximo de campos distintos que ella puede visitar a lo largo de una ruta comenzando y terminando en el campo1, donde ella puede recorrer un camino en su ruta en la dirección incorrecta. Bessie puede únicamente ir hacia atrás a lo más una vez en su desplazamiento. En particular, ella no puede tomar el mismo camino hacia atrás dos veces.

Entrada

La primera línea de la entrada contiene ~N~ y ~M~, dando el número de campos y el número de caminos en un sentido.

Cada una de las siguientes ~M~ líneas describen un camino de un sentido. Cada línea contiene dos números de campos distintos ~X~ y ~Y~, correspondiente a un camino de ~X~ a ~Y~. El mismo camino nunca aparecerá más de una vez.

Salida

Una sola línea indicando el máximo número de campos distintos que Bessie puede visitar a lo largo de una ruta comenzando y terminando en el campo 1, dado que ella puede recorrer a lo más un camino a lo largo de la ruta en la dirección incorrecta.

Restricciones

• ~1 \leq N, M \leq 100,000~

Ejemplo de Entrada

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

Ejemplo de Salida

6

Notas de la Salida: Aquí hay un diagrama ASCCII de la entrada ejemplo:

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

Bessie puede visitar los campos ~1, 2, 4, 7, 2, 5, 3, 1~ recorriendo hacia atrás el camino entre 5 y 3. Cuando ella llega a 3 no puede llegar a 6 sin seguir otro camino hacia atrás.

USACO 2015 January Contest, Gold Problem 3. Grass Cownoisseur.