给定 $n$ 棵有根树 $T_1, T_2, \dots, T_n$，求两个排列 $p_1, p_2, \dots, p_n$ 和 $q_1, q_2, \dots, q_n$，使得 $T_{p_1} \times T_{p_2} \times \dots \times T_{p_n}$ 的直径最大，且 $T_{q_1} \times T_{q_2} \times \dots \times T_{q_n}$ 的直径最小。

对于两棵有根树 $A$ 和 $B$，它们的树积 $T = A \times B$ 定义如下：复制树 $A$，然后对于其中的每个顶点 $x$，复制一份 $B$ 并将其根与顶点 $x$ 合并。示例如下：

可以证明树积满足结合律：$(A \times B) \times C = A \times (B \times C)$。因此，三个或更多树的乘积中的括号可以省略。

回顾： 树是一个无环连通图。有根树有一个特殊的顶点称为根。顶点 $v$ 的父节点是从根到 $v$ 的路径上除 $v$ 之外的最后一个顶点。 有根树的直径是树中最长简单路径的长度，其中路径长度为路径上的边数。

输入格式

输入包含多个测试用例。第一行包含一个整数 $T$，表示测试用例的数量。每个测试用例：

第一行包含一个整数 $n$ ($1 \le n \le 10^6$)，表示有根树的数量。

接下来的 $n$ 行，每行首先是一个整数 $m_i$ ($1 \le m_i \le 10^5$)，表示第 $i$ 棵有根树的顶点数。随后是同一行上的 $m_i$ 个整数 $p_{i,1}, p_{i,2}, \dots, p_{i,m_i}$ ($0 \le p_{i,j} \le m_i$)，其中第 $j$ 个整数表示第 $j$ 个顶点的父节点。树的根节点的父节点为 $0$。

保证所有测试用例的 $m_i$ 之和不超过 $10^6$。

输出格式

对于每个测试用例，输出两个整数：最大直径和最小直径，按此顺序输出。

样例

输入 1

2
3
5 0 1 2 1 4
3 2 0 2
2 2 0
2
1 0
1 0

输出 1

8 7
0 0

说明

对于第一个样例测试用例，$T_1 \times T_2 \times T_3$ 将提供最大直径，而 $T_3 \times T_2 \times T_1$ 将提供最小直径。