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 water 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.
1.
i be the highest order of all its upstream nodes.
If just one upstream node has order i,
then this node also has order i.
If two or more upstream nodes have order i,
then this node has order i+1.
In the picture to the right,
the Strahler order is three (3).
Note: 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 Strahler order is the Amazon
with order 12.
The highest in the U.S. is the Mississippi with order 10.
Node M is the mouth of the river.
It has no outgoing edges.
The first line of input contains a single integer T
(1 ≤ T ≤ 1000),
which is the number of test cases that follow.
Each data set should be processed identically and independently.
Each data set consists of multiple lines of input.
The first line of each data set contains
three positive integers:
K, M and P
(2 ≤ M ≤ 1000).
K is the data set number.
M is the number of nodes in the graph.
And P is the number of edges.
The first line is followed by P lines,
each describing an edge of the graph.
The line will contain two positive integers,
A and B,
indicating that water flows
from node A to node B
(1 ≤ A & B ≤ M).
Node M is the mouth of the river.
It has no outgoing edges.
1 1 7 8 1 3 2 3 6 4 3 4 3 5 6 7 5 7 4 7
For each data set, there is a single line of output. The line consists of the data set number, a single space, and then the order of the river system.
1 3