Ферма Джона состоит из 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---^