给定一棵有 $n$ 个节点的有根树，根节点为 $1$，且满足 $p_i < i$，其中 $p_i$ 是 $i$ 的父节点。

对于每个节点 $u$ 的所有子节点 $v$，我们将提供仅考虑 $v$ 及其子树中的节点所构成的树的重心索引，注意我们不会给出 $v$ 的索引。如果一棵树有两个重心，我们将给出在原树中深度更深的那一个。你的任务是构造一棵满足上述条件的树。

树的重心：如果从树中选择并移除一个节点，树将被分成若干个子树。统计每个子树的节点数，并记录其中的最大值。在考虑树中所有节点时，使得该最大值最小的节点被称为整棵树的重心。

输入格式

第一行包含一个整数 $T$ ($1 \le T \le 10^5$)，表示测试用例的数量。

对于每个测试用例，第一行包含一个整数 $n$ ($2 \le n \le 2 \cdot 10^5$)，表示树的节点数。

接下来的 $n$ 行，每行首先给出一个整数 $c_i$ ($1 \le c_i \le n$)，表示节点 $i$ 的子节点数量，随后是 $c_i$ 个整数 $p_{i,j}$ ($1 \le p_{i,j} \le n$)，表示由 $i$ 的第 $j$ 个子节点及其子树中的节点所构成的树的重心索引。

所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，输出 $n - 1$ 行。第 $i$ 行应输出两个整数 $u, v$ ($1 \le u, v \le n, u \neq v$)，表示树中的一条边 $(u, v)$。

测试数据保证有解。如果存在多个合法的解，输出其中任意一个即可。

样例

输入 1

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

输出 1

2 3
1 2
1 4
2 3
1 2