풀 미식가 소

농부 존은 소가 풀을 뜯는 경로를 관리하려고 농장 곳곳에 일방통행 길을 깔았다. 농장에는 $1$번부터 $N$번까지 번호가 붙은 밭이 $N$개 있고, 길 하나는 밭 두 개를 잇는다. 밭 $X$에서 밭 $Y$로 가는 길이 있으면 소는 $X$에서 $Y$로 갈 수 있지만 $Y$에서 $X$로는 갈 수 없다.

소 베시는 되도록 많은 밭에서 풀을 뜯고 싶어 한다. 베시는 하루를 $1$번 밭에서 시작하고, 밭 여러 개를 차례로 지난 뒤 다시 $1$번 밭으로 돌아온다. 같은 밭을 여러 번 지나도 그곳의 풀은 한 번만 먹으므로, 베시는 경로에 나오는 서로 다른 밭의 개수를 최대로 만들려고 한다.

일방통행 규칙은 베시가 하루에 들를 수 있는 밭의 수를 줄인다. 그래서 베시는 규칙을 어기고 길 하나를 거꾸로 지나가면 풀을 얼마나 더 먹을 수 있을지 궁금해한다. $1$번 밭에서 출발해 $1$번 밭으로 돌아오는 경로 중 길을 최대 한 번 거꾸로 지날 수 있을 때, 지나는 서로 다른 밭 개수의 최댓값을 구하시오. 거꾸로 가는 이동은 하루에 한 번만 할 수 있으므로, 같은 길을 두 번 거꾸로 지날 수도 없다.

첫째 줄에 밭의 개수 $N$과 일방통행 길의 개수 $M$이 주어진다. ($1 \le N, M \le 100{,}000$)

다음 $M$개 줄에는 각각 길 하나가 서로 다른 밭 번호 $X$와 $Y$로 주어진다. $X$에서 $Y$로 가는 길이 있다는 뜻이다. 같은 길이 두 번 주어지는 경우는 없다.

$1$번 밭에서 출발해 $1$번 밭으로 돌아오고 길을 최대 한 번 거꾸로 지나는 경로에서, 지나는 서로 다른 밭 개수의 최댓값을 한 줄에 출력한다.

첫 번째 예제의 농장을 그림으로 나타내면 다음과 같다.

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

베시는 $5$번과 $3$번을 잇는 길을 거꾸로 지나서 $1, 2, 4, 7, 2, 5, 3, 1$ 순서로 다닐 수 있다. $3$번 밭에 도착한 다음에는 길을 한 번 더 거꾸로 지나지 않고서는 $6$번 밭에 갈 수 없다.