문제
지리학에서 강물의 계통시스템(하계 - river system, 河系) 문제는 방향이 있는 그래프 문제로 바꾸어 생각할 수 있다. 강의 구간은 간선(edge)으로 강물의 근원지와 강물이 합쳐지거나 갈라지는 곳, 그리고 강 하구는 정점(vertex)으로 표시할 수 있다. 아래 그림을 보자.
위 그림에서 원안의 숫자는 노드의 번호이며 7번 노드는 강 하구이다. 사각형 안의 숫자는 그 노드의 Strahler order(계급)을 의미한다.
강물의 계통시스템(하계 - river system, 河系)에서 Strahler Order는 아래와 같이 계산된다. - 근원지의 order(계급)은 1이다. - 근원지가 아닌 다른 모든 노드에 대하여 다음과 같이 order를 계산한다.현재 노드의 모든 상위노드의 order(계급)중에 최대값을 mx라고 할 때, mx를 가진 상위노드가1개 뿐이라면 현재 노드의 order(계급)은 mx이다.두 개 이상이라면 현재 노드의 order(계급)은 mx + 1 이다. - 이 때 전체 강물의 계통시스템의 Strahler Order는 강 하구의 order로 한다.위의 예에서 Strahler Order는 3이 된다.
이 시스템은 지리학에서 실제 사용하고 있으며 전 세계에서 가장 큰 Strahler Order는 12로서 아마존 강이라고 한다. 미국에 있는 미시시피 강의 Strahler Order는 10이라고 한다.
입력
첫 행에 노드의 수 N(1 <= N <= 1000)과 간선의 수 E가 입력된다.
다음 E개의 행에 간선의 정보 Ai와 Bi가 입력되는데 노드 Ai로부터 노드 Bi로 물이 흐른다는 의미이다.
(1 ≤ A, B ≤N) 이고 강 하구의 번호는 N이다.
출력
주어진 정보에 대하여 전체 강물의 계통시스템의 Strahler Order를 출력하시오.
예제
7 8
1 3
2 3
6 4
3 4
3 5
6 7
5 7
4 7
3
출처
Greater NY
로그인해야 코드를 작성할 수 있어요.