SPOJ in Gyumri

   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.

Note: The number in a box is the order. The number in a circle is the node number.

   The Strahler order of a river system is computed as follows.

• The order of each source node is 1.
• For every other node, let 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.

   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 picture above, the Strahler order is three (3).

   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 12.  The highest in the U.S. is the M ississippi, with order 10.

   Node M is the mouth of the river. It has no outgoing edges.

Input

   The first line of input contains a single integer K, (1 ≤ K ≤ 1000), which is the number of data sets 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.

Output

   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.

Examples