소 수 급증으로 헛간 길이 혼잡합니다. Farmer John은 착유 ‘교통 체증’을 줄이려 병목을 조사합니다.

$M$($1 \le M \le 50,000$)단방향 길은 번호 $1..N$인 $N$($1 \le N \le 5,000$)교차점 중 서로 다른 둘을 잇고 헛간은 $N$입니다. 큰 번호로 가므로 순환이 없고 모두 헛간에 갑니다. 한 쌍에 여러 길도 가능합니다.

착유 러시아워에 각 방목점에서 헛간으로 갑니다. 방목점은 들어오는 길 없는 교차점들입니다. ‘경로’는 그곳부터 헛간까지 길 순서입니다.

한 길을 포함하는 가능한 경로 수의 최대를 구해 가장 바쁜 길을 찾으세요. 답은 부호 있는 32비트 정수에 들어갑니다.

입력

1번째 줄: 공백 구분 정수 $N$, $M$.

$2..M+1$번째 줄: 공백 구분 두 교차점.

출력

1번째 줄: 한 길을 지나는 최대 경로 수.

예제

입력 1

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

출력 1

4

참고

헛간까지 네 가능한 경로:

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

출처: USACO 2007년 3월.