방목을 더 잘 관리하려고 Farmer John은 농장 곳곳에 일방통행 소 길을 만들었다. $N$개의 들판은 $1..N$으로 번호를 매겼고 각 길은 둘을 잇는다. $X$에서 $Y$로 가는 길은 그 방향만 허용하고 반대는 허용하지 않는다.

Bessie는 최대한 많은 들판의 풀을 먹고 싶다. 매일 들판 $1$에서 출발해 여러 들판을 방문하고 마지막에 $1$로 돌아온다. 서로 다른 들판 수를 최대화하며, 여러 번 방문해도 그곳 풀은 한 번만 먹는다.

일방통행 제한이 방문 수를 줄여서 마음에 들지 않는다. 규칙을 어기고 최대 한 번 길을 역방향으로 가면 얼마나 먹을 수 있을까? 들판 $1$에서 시작하고 끝나며 최대 한 번 역방향 이동하는 경로의 서로 다른 들판 최대 수를 구하라. 전체 여행에서 역방향은 최대 한 번뿐이며 같은 길도 두 번 역방향으로 갈 수 없다.

입력

첫 줄은 들판 수 $N$과 길 수 $M$($1 \leq N, M \leq 100,000$)을 포함한다.

다음 $M$개 줄은 서로 다른 번호 $X$, $Y$로 $X$에서 $Y$의 길을 나타낸다. 같은 길은 중복되지 않는다.

출력

$1$에서 시작해 $1$로 돌아오며 최대 한 번 역방향 이동할 때 서로 다른 들판 최대 수를 한 줄로 출력한다.

예제

입력 1

7 10
1 2
3 1
2 5
2 4
3 7
3 5
3 6
6 5
7 2
4 7

출력 1

6

참고

예제 입력의 ASCII 그림이다.

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

$5$와 $3$ 사이 길을 역방향으로 가서 $1,2,4,7,2,5,3,1$을 방문할 수 있다. $3$에 도착하면 다른 역방향 길 없이는 $6$에 갈 수 없다.

문제 출제: Mark Gordon, 2015