문제

현성이는 알고리즘 동아리 축제가 열리는 장소를 탐방하려고 한다. 축제 장소는 $1$번부터 $N$번까지 번호가 매겨진 $N$개의 구역으로 나뉘어 있으며, 각 구역은 일방통행 길로 연결되어 있다. 예를 들어, 어떤 길이 $X$번 구역에서 $Y$번 구역으로 연결된다면, 현성이는 $X$에서 $Y$로는 이동할 수 있지만 $Y$에서 $X$로는 이동할 수 없다.

현성이는 가능한 한 많은 구역을 방문하여 축제를 즐기고 싶어 한다. 현성이는 항상 $1$번 구역에서 출발하여 여러 구역을 방문한 뒤, 다시 $1$번 구역으로 돌아와야 한다. 현성이는 경로상에 포함된 서로 다른 구역의 개수를 최대화하려고 한다. 같은 구역을 여러 번 방문할 수 있지만, 구역의 개수를 셀 때는 한 번만 포함한다.

일방통행 규칙 때문에 방문할 수 있는 구역의 수가 적은 것이 아쉬웠던 현성이는, 딱 한 번 규칙을 어기고 길 하나를 역방향으로 이동하기로 했다. 즉, 원래 $X$에서 $Y$로 가는 일방통행 길을 $Y$에서 $X$ 방향으로 한 번만 거슬러 올라갈 수 있다. 역방향 이동은 전체 경로에서 최대 한 번만 가능하며, 동일한 길을 두 번 역방향으로 이동할 수는 없다.

$1$번 구역에서 출발하여 다시 $1$번 구역으로 돌아오는 경로 중, 최대 한 번의 역방향 이동을 포함했을 때 방문할 수 있는 서로 다른 구역의 최대 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 구역의 수 $N$과 일방통행 길의 수 $M$이 공백으로 구분되어 주어진다. ($1 \le N, M \le 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