在地理学中，河流系统可以用有向图来表示。每条河流段都是一条边，边的方向与水流方向一致。节点要么是河流段的源头（例如湖泊或泉水），要么是河流段汇合或分流的地方，或者是河流的入海口。

注：方框中的数字是阶数。圆圈中的数字是节点编号。

河流系统的 Strahler order 计算方法如下：

• 每个源头节点的阶数为 $1$。
• 对于其他每个节点，设 $i$ 为其所有上游节点中的最高阶数。如果只有一个上游节点的阶数为 $i$，则该节点的阶数也为 $i$。如果有两个或更多上游节点的阶数为 $i$，则该节点的阶数为 $i+1$。

整个河流系统的阶数即为入海口节点的阶数。在本题中，河流系统将只有一个入海口。在上图中，Strahler order 为 $3$。

你需要编写一个程序来确定给定河流系统的阶数。

现实中阶数最高的河流是亚马逊河，阶数为 $12$。美国阶数最高的河流是密西西比河，阶数为 $10$。

节点 $M$ 是河流的入海口，它没有出边。

输入格式

输入的第一行包含一个整数 $K$ ($1 \le K \le 1000$)，表示随后数据组的数量。每组数据应独立处理。

每组数据包含多行输入。每组数据的第一行包含三个正整数 $K$、$M$ 和 $P$ ($2 \le M \le 1000$)。$K$ 是数据组编号，$M$ 是图中的节点数，$P$ 是边的数量。接下来的 $P$ 行，每行描述图中的一条边。该行包含两个正整数 $A$ 和 $B$ ($1 \le A, B \le M$)，表示水从节点 $A$ 流向节点 $B$。节点 $M$ 是河流的入海口，它没有出边。

输出格式

对于每组数据，输出一行。该行包含数据组编号、一个空格以及该河流系统的阶数。

样例

输入 1

1
1 7 8
1 3
2 3
6 4
3 4
3 5
6 7
5 7
4 7

输出 1

1 3