Pour mieux gérer le pâturage, Farmer John a installé des chemins à sens unique. La ferme a $N$ champs numérotés $1..N$, et chaque chemin relie deux champs. Un chemin de $X$ à $Y$ permet d’aller de $X$ à $Y$, mais pas l’inverse.

Bessie aime manger dans le plus de champs possible. Elle commence chaque jour au champ $1$, visite une suite de champs et revient au $1$. Elle maximise le nombre de champs distincts, puisqu’elle ne mange l’herbe qu’une fois dans un champ visité plusieurs fois.

Elle n’aime pas le sens unique, qui réduit ses visites. Combien pourra-t-elle manger en enfreignant la règle sur au plus un chemin ? Calculez le maximum de champs distincts d’un parcours commençant et finissant au $1$, avec au plus un passage à contresens. Un seul passage à contresens est autorisé au total : même le même chemin ne peut être pris deux fois à l’envers.

Entrée

La première ligne contient le nombre de champs $N$ et de chemins $M$ ($1 \leq N, M \leq 100,000$).

Les $M$ lignes suivantes donnent deux numéros distincts $X$, $Y$ pour un chemin de $X$ à $Y$. Aucun chemin n’est répété.

Sortie

Affichez en une ligne le maximum de champs distincts sur un parcours du $1$ au $1$ avec au plus un passage à contresens.

Exemples

Entrée 1

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

Sortie 1

6

Remarque

Voici un dessin ASCII de l’exemple :

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

Elle peut visiter $1,2,4,7,2,5,3,1$ en prenant à contresens le chemin entre $5$ et $3$. Au $3$, elle ne peut atteindre $6$ sans un autre contresens.

Auteur du problème : Mark Gordon, 2015