Чтобы лучше управлять выпасом, Farmer John проложил односторонние коровьи тропы. На ферме $N$ полей с номерами $1..N$, каждая тропа соединяет пару. Если она ведёт из $X$ в $Y$, можно идти из $X$ в $Y$, но не обратно.

Bessie любит есть траву на как можно большем числе полей. Утром начинает в поле $1$, проходит последовательность полей и к вечеру возвращается в $1$. Она максимизирует число различных полей: траву в повторно посещённом поле ест лишь раз.

Односторонность ей не нравится, поскольку уменьшает число доступных полей. Сколько травы она съест, если нарушит правила и пройдёт не более одной тропы против направления? Найдите максимум различных полей на маршруте из $1$ обратно в $1$ с не более одним обратным проходом. За всё путешествие идти обратно можно лишь раз, даже одну тропу нельзя пройти обратно дважды.

Входные данные

Первая строка содержит число полей $N$ и троп $M$ ($1 \leq N, M \leq 100,000$).

Следующие $M$ строк задают тропы: два различных номера $X$, $Y$ означают путь из $X$ в $Y$. Тропы не повторяются.

Выходные данные

Выведите одной строкой максимум различных полей на маршруте из $1$ в $1$ с не более одним обратным проходом.

Примеры

Входные данные 1

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

Выходные данные 1

6

Примечание

ASCII-схема примера:

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

Она может посетить $1,2,4,7,2,5,3,1$, пройдя обратно тропу между $5$ и $3$. Из $3$ она не может попасть в $6$ без ещё одного обратного прохода.

Автор задачи: Mark Gordon, 2015