소 교통량

목장의 젖소 개체 수가 급증하면서 외양간으로 이어지는 소 길에 심각한 혼잡이 발생했다. 존 아저씨는 착유 시간의 '교통 체증'을 해소하기 위해 병목이 되는 길을 찾는 조사를 하기로 했다.

목초지는 $M$개의 일방통행 길로 이루어진 연결망이며 ($1 \le M \le 50{,}000$), 각 길은 $1$부터 $N$까지 번호가 매겨진 $N$개의 교차점 ($1 \le N \le 5{,}000$) 중 서로 다른 두 교차점을 잇는다. 외양간은 $N$번 교차점에 있다. 모든 길은 번호가 더 작은 교차점에서 번호가 더 큰 교차점으로 향한다. 따라서 순환(사이클)이 존재하지 않으며, 결국 모든 길은 외양간으로 이어진다. 두 교차점 사이에는 둘 이상의 길이 있을 수도 있다.

착유 시간의 혼잡한 시간대가 되면 소들은 각자 풀을 뜯던 자리에서 출발해 외양간으로 향한다. 풀 뜯는 자리란 들어오는 길이 하나도 없는 교차점들을 말한다. 각 소는 '경로'를 따라가는데, 경로란 풀 뜯는 자리에서 외양간까지 이어지는 길들의 나열이다.

어떤 하나의 길을 지나는 경로가 최대 몇 개가 될 수 있는지를 구해 가장 붐비는 길을 찾아 도와주자. 정답은 부호 있는 32비트 정수 범위에 들어옴이 보장된다.

• 첫째 줄: 공백으로 구분된 두 정수 $N$과 $M$.
• 둘째 줄부터 $M+1$째 줄까지: 하나의 일방통행 길을 나타내는 두 정수. 길은 번호가 더 작은 교차점에서 번호가 더 큰 교차점으로 향한다.

• 첫째 줄: 어떤 하나의 길을 지나는 경로의 최대 개수.