농장에서 소들의 마리수가 증가함에 따라 외양간으로 향하는 소의 도로에 심각한 혼잡이 발생하였다.

농부 창호는 우유를 짜는 시간대의 교통체증을 완화시키기 위해 병목지점을 찾는 방법을 만들어 보고자 했다.

목장은 M(1≤M≤50,000)개의 일방통행 도로를 가진 네트워크를 포함하며,

각각의 도로는 1~N까지 번호가 매겨진 N(1≤N≤5,000)개의 교차점 중 서로 다른 두 개의 교차점을 연결한다.

외양간은 N번 교차점에 있다.

각각의 도로는 한 교차점에서 그 교차점보다 표기숫자가 높은 교차지점으로 연결 된다.

(예컨데 3->4연결은 있으나 4->3연결은 있을 수 없다.)

따라서 도로에는 사이클이 없으며 모든 길들은 외양간에 이어지게 된다.

한 쌍의 교차점들은 한 개 이상의 도로로 연결 될 수 있다. 우유를 짜는 혼잡한 시간대에, 소들은 그들 각각의 풀을 뜯는 장소에서 시작하여 외양간을 향해 간다. 풀 뜯는 장소들은 교차점 중에서 그 어떤 도로도 해당 교차점을 향해서 들어가지 않는 교차점들이다.

창호를 돕기 위하여 다음과 같은 작업을 해보자.

소들이 목초지로부터 외양간으로 이동하는 경로들중 가장 많은 경로에 포함되는 도로를 찾아

이 도로를 지나는 경로의 수를 구하는 프로그램을 작성하자.

입력예 1번에 대한 설명을 하자면 다음과 같다.

목초지로부터 외양간에 이르는 경로는 아래와 같다.

1 3 4 6 7

1 3 5 6 7
2 3 4 6 7

2 3 5 6 7

이 중에 가장 많이 포함된 도로는 6번 7번을 잇는 도로이고 모두 4개의 경로에 포함된다.

정답은 2^31 -1 이하이다.

jams timer 1s memory 64MB

jams 1s 64MB