Strahler order

In geology a river system can be drawn as a directed graph. A river is an edge, and the direction the water flows is the direction of the edge. A node is a place where a river begins, such as a spring or a lake, a place where rivers merge or split, or the place where a river meets the sea. Water only runs downstream, so no path returns to a node it has already passed.

The order of the river drawn by edge $(u, v)$ is the order of node $u$ that the river flows out of. The Strahler order of each node is found as follows.

• A node with no incoming river is the source of a river, and its order is $1$.
• For any other node, let $i$ be the largest order among its incoming rivers. If exactly one incoming river has order $i$, the node has order $i$. If two or more do, the node has order $i + 1$.

The order of the river system equals the order of the node that meets the sea. There is always exactly one such node, and it is node $M$.

Given a river system, write a program that computes its Strahler order.

Among real rivers the Amazon has the largest Strahler order at $12$, and the largest in the United States is the Mississippi at $10$.

The first line contains the number of test cases $T$ $(1 \le T \le 1000)$.

The first line of each test case contains $K$, $M$, and $P$. $K$ is the test case number, $M$ is the number of nodes, and $P$ is the number of edges. $(2 \le M \le 1000)$

Each of the next $P$ lines contains one edge as $A$ and $B$, meaning water flows from $A$ to $B$. $(1 \le A, B \le M)$

Node $M$ is always the node that meets the sea, and no edge leads out of node $M$.

For each test case, print the test case number $K$ and the Strahler order of that river system on one line, separated by a single space.