Знаток травы
Знаток травы
Ферма Джона состоит из n полей, последовательно пронумерованных от 1 до n, соединённых односторонними дорожками. То есть, если есть дорожка из поля x в поле y, то корова может пройти из поля x в поле y и не может пройти из поля y в поле x.
Беси хочет поесть траву на как можно большем количестве полей. Она всегда начинает на поле 1 и посещает последовательно поля всегда возвращаясь в поле 1 в конце дня. Она старается максимизировать количество различных полей в своём маршруте, поскольку она съедает всю траву в первый заход, и если она попадает на поле второй и последующие разы, там уже нечего есть.
Понятно, что Бесси недовольна тем,. что дорожки односторонние. И она хочет узнать, сколько травы она сможет съесть, если одну из дорожек пройдёт в обратном направлении.
Пожалуйста, определите максимальное количество различных полей, которые она сможет посетить по маршруту, который начинается и заканчивается в поле 1. при условии, что она пройдёт не более одной дорожки в обратном направлении. В том числе, она не может пройти по одной и той же дорожке в противоположном направлении дважды.
Входные данные
Первая строка содержит целые числа n и m (1 ≤ n, m ≤ 105
), определяющие количество полей и количество односторонних дорожек.
Последующие m строк каждая описывают одностороннюю дорожку. Каждая строка содержит числа x и y, соответствующие дорожке из поля x в поле y. Одна и та же дорожка не появится более чем один раз.
Выходные данные
Одна строка указывающая максимальное количество различных полей, которые Беси сможет посетить начиная и заканчивая в поле 1 при условии, что она может не более одной дорожки пройти в обратном направлении.
Note
Беси может посетить поля 1, 2, 4, 7, 2, 5, 3, 1 использовав обратную дорожку между пастбищами 5 и 3. Когда она прибывает в 3, она не может достичь 6 без использования другой обратной дорожки.
v---3-->6
7 |\ |
^\ v \ |
| \ 1 \|
| \| v
| v 5
4<--2---^
7 10 1 2 3 1 2 5 2 4 3 7 3 5 3 6 6 5 7 2 4 7
6