Знавець трави#11194

Знавець трави

1 секунда

128 мегабайтів

Дуже складна

Прагнучи краще контролювати маршрути випасу своїх корів, фермер Джон прокладав по всій своїй фермі односторонні дороги для корів. Ферма складається з $n$ полів, пронумерованих від $1$ до $n$ , причому кожна одностороння дорога з'єднує деяку пару полів. Наприклад, якщо дорога веде з поля $x$ до поля $y$ , корови можуть рухатися з $x$ до $y$ , але не з $y$ до $x$ .

Бессі, як ми всі знаємо, любить їсти траву на якомога більшій кількості полів. На початку дня вона завжди знаходиться на полі $1$ і слідує деяким маршрутом, який в кінці дня приводить її назад на поле $1$ . Вона хоче максимізувати кількість різних полів, які вона відвідує по дорозі, оскільки на кожному з них вона може поїсти трави. Якщо вона відвідує одне й те саме поле кілька разів, трава на ньому враховується лише один раз.

Як можна собі уявити, Бессі не дуже задоволена обмеженням на односторонній рух по дорогах фермера Джона, оскільки воно обмежує кількість різних полів, які вона може відвідати за день. Вона хоче дізнатися, скільки трави вона зможе з'їсти, якщо їй дозволять порушити правила і проїхати максимум по одній дорозі в неправильному напрямку.

Визначте максимальну кількість різних полів, які Бессі може відвідати, слідуючи маршрутом, що починається і закінчується на полі $1$ , якщо їй дозволено проїхати максимум по одній дорозі в неправильному напрямку. За всю подорож Бессі може рухатися в неправильному напрямку не більше одного разу. Зокрема, вона не може двічі проїхати по одній і тій самій дорозі у зворотному напрямку.

Вхідні дані

У першому рядку містяться два числа: $n$ і $m (1 \leq n, m \leq 1 0^{5})$ m~(1 \le n, m \le 10^5), де $n$ — кількість полів, а $m$ — кількість односторонніх доріг.

Наступні $m$ рядків описують односторонні дороги. Кожен рядок містить два різних номери полів $x$ і $y$ , що означає, що корови можуть рухатися з поля $x$ до поля $y$ . Одна й та сама дорога не зустрічається у вхідних даних більше одного разу.

Вихідні дані

Виведіть одне ціле число — максимальну кількість різних полів, які Бессі може відвідати за маршрутом, що починається і закінчується на полі $1$ , якщо їй дозволено проїхати максимум по одній дорозі в неправильному напрямку.

Приклади

Бессі може відвідати поля $1, 2, 4, 7, 2, 5, 3$ 1, 2, 4, 7, 2, 5, 3 і $1$ , проїхавши у зворотному напрямку по дорозі між полями $5$ і $3$ . Однак, опинившись на полі $3$ , вона не зможе дістатися до поля $6$ , не проїхавши ще по одній дорозі у зворотному напрямку.

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

Приклад 1