Strahler 순서

지질학에서 하천계는 방향 그래프로 나타낼 수 있다. 강은 간선이고, 물이 흐르는 방향이 간선의 방향이 된다. 노드는 샘이나 호수처럼 강이 시작하는 곳, 강이 합쳐지거나 갈라지는 곳, 바다와 만나는 곳이다. 물은 상류에서 하류로만 흐르므로 이미 지나온 노드로 되돌아오는 경로는 없다.

간선 $(u, v)$가 나타내는 강의 순서는 그 강이 흘러나오는 노드 $u$의 순서와 같다. 각 노드의 Strahler 순서는 다음과 같이 구할 수 있다.

• 들어오는 강이 하나도 없는 노드는 강의 근원이고, 순서는 $1$이다.
• 나머지 노드는 들어오는 강의 순서 중 가장 큰 값을 $i$라고 할 때, 순서가 $i$인 강이 하나뿐이면 순서가 $i$이고, 둘 이상이면 $i + 1$이다.

하천계의 순서는 바다와 만나는 노드의 순서와 같다. 바다와 만나는 노드는 항상 하나이며, 노드 $M$이 그 노드다.

하천계의 정보가 주어졌을 때, Strahler 순서를 구하는 프로그램을 작성하시오.

실제 강 중에서는 아마존강의 Strahler 순서가 $12$로 가장 크고, 미국에서 가장 큰 값을 갖는 강은 미시시피강으로 $10$이다.

첫째 줄에 테스트 케이스의 수 $T$ $(1 \le T \le 1000)$가 주어진다.

각 테스트 케이스의 첫째 줄에는 $K$, $M$, $P$가 주어진다. $K$는 테스트 케이스 번호, $M$은 노드의 수, $P$는 간선의 수이다. $(2 \le M \le 1000)$

다음 $P$개 줄에는 간선의 정보 $A$, $B$가 한 줄에 하나씩 주어지며, $A$에서 $B$로 물이 흐른다는 뜻이다. $(1 \le A, B \le M)$

노드 $M$은 항상 바다와 만나는 노드이며, 노드 $M$에서 밖으로 향하는 간선은 존재하지 않는다.

각 테스트 케이스마다 테스트 케이스 번호 $K$와 그 하천계의 Strahler 순서를 공백 하나로 구분해 한 줄에 출력한다.