Ферма Джона состоит из N полей, последовательно пронумерованных
от 1 до N, соединённых односторонними дорожками. То есть, если есть
дорожка из поля X в поле Y, то корова может пройти из поля X в
поле Y и не может пройти из поля Y в поле X.
Беси хочет поесть траву на как можно большем количестве полей.
Она всегда начинает на поле 1 и посещает последовательно поля
всегда возвращаясь в поле 1 в конце дня. Она старается максимизировать
количество различных полей в своём маршруте, поскольку она съедает
всю траву в первый заход, и если она попадает на поле второй и
последующие разы, там уже нечего есть.
Понятно, что Бесси недовольна тем,. что дорожки односторонние.
И она хочет узнать, сколько травы она сможет съесть, если одну из
дорожек пройдёт в обратном направлении.
Пожалуйста, определите максимальное количество различных полей,
которые она сможет посетить по маршруту, который начинается и
заканчивается в поле 1. при условии, что она пройдёт не более
одной дорожки в обратном направлении. В том числе, она не может
пройти по одной и той же дорожке в противоположном направлении
дважды.
Формат входных данных
Первая строка ввода содержит целые числа N и M, определяющие
количество полей и количество односторонних дорожек
(1 <= N, M <= 100,000).
Последующие M строк каждая описывают одностороннюю дорожку.
Каждая строка содержит числа X и Y, соответствующие дорожке
из поля X в поле Y.
Одна и та же дорожка не появится более чем один раз.
Формат выходных данных
Одна строка указывающая максимальное количество различных полей,
которые Беси сможет посетить начиная и заканчивая в поле 1 при
условии, что она может не более одной дорожки пройти в обратном
направлении.
Примечание
Это рисунок ввода
v---3-->6
7 |\ |
^\ v \ |
| \ 1 \|
| \| v
| v 5
4<--2---^
Беси может посетить поля 1, 2, 4, 7, 2, 5, 3, 1
использовав обратную дорожку между пастбищами 5 и 3.
Когда она прибывает в 3, она не может достичь 6
без использования другой обратной дорожки.