문제
농장에서 소들의 마리수가 증가함에 따라 외양간으로 향하는 소의 도로에 심각한 혼잡이 발생하였다.
농부 창호는 우유를 짜는 시간대의 교통체증을 완화시키기 위해 병목지점을 찾는 방법을 만들어 보고자 했다.
목장은 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 72 3 4 6 7
2 3 5 6 7
이 중에 가장 많이 포함된 도로는 6번 7번을 잇는 도로이고 모두 4개의 경로에 포함된다.
정답은 2^31 -1 이하이다.
입력
첫 번째 줄에는 공백을 사이에 두고 N과 M이 주어진다. 두 번째 줄부터 M+1 번째 줄엔 공백을 간격으로 도로가 연결하는 두 교차점의 번호가 주어진다.
출력
임의의 한 도로를 지나는 최대의 길 숫자를 출력한다.
예제1
77
13
34
35
46
23
56
67
4