Strahler Order#6389
In geology, a river system can be represented as a directed graph. Each river segment is an edge; with the edge pointing the same way the waters flows. Nodes are either the source of a river segment (for example, a lake or spring), where river segments merge or diverge, or the mouth of the river.
The Strahler order of a river system is computed as follows.
The order of each source node is .
For every other node, let be the highest order of all its upstream nodes. If just one upstream node has order , then this node also has order . If two or more upstream nodes have order , then this node has order i + 1.
The order of the entire river system is the order of the mouth node. In this problem, the river system will have just one mouth. In the given example, the Strahler order is three (3).
The number in a box is the order. The number in a circle is the node number.
You must write a program to determine the order of a given river system.
The actual river with the highest order is the Amazon, with order . The highest in the U.S. is the Mississippi, with order .
The first line contains the number (1 \leq t \leq 1000) of data sets that follow. Each data set should be processed independently.
Each data set consists of multiple lines. The first line of each data set contains three positive integers , and (2 \leq m \leq 1000). is the data set number. is the number of nodes in the graph and is the number of edges. The first line is followed by lines, each describing an edge of the graph. The line will contain two positive integers and , indicating that water flows from node to node (1 \leq a, b \leq m). Node is the mouth of the river. It has no outgoing edges.
For each data set there is a single line of output. The line consists of the data set number, a single space and the order of the river system.
Example 1