题目描述

给定$N-1$个$\\{1,2,...,N\\}$的子集。设第$i$个集合为$E_i$。

从每个集合$E_i$中选择两个不同的元素$u_i$和$v_i$，构建一个$N$个顶点和$N-1$条边的图$T$，其中顶点集为$\\{1,2,..,N\\}$，边集为$(u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1})$。请确定是否可以通过正确选择$u_i$和$v_i$使得$T$成为一棵树。如果可以，另外找到一个满足条件的$(u_1,v_1),(u_2,v_2),...,(u_{N-1},v_{N-1})$实例，使得$T$实际上是一棵树。

约束条件

• $2 \leq N \leq 10^5$
• $E_i$是$\\{1,2,..,N\\}$的子集。
• $|E_i| \geq 2$
• $|E_i|$的总和最多为$2 \times 10^5$。

输入

输入以如下格式从标准输入给出：

$N$ $c_1$ $w_{1,1}$ $w_{1,2}$ $w_{1,3}$ ... $w_{1,c_1}$ $:$ $c_{N-1}$ $w_{N-1,1}$ $w_{N-1,2}$ $w_{N-1,3}$ ... $w_{N-1,c_{N-1}}$

这里，$c_i$代表$E_i$中元素的个数，$w_{i,1},...,w_{i,c_i}$是$c_i$个元素。其中，$2 \leq c_i \leq N$，$1 \leq w_{i,j} \leq N$，且$w_{i,j} \neq w_{i,k}$ ($1 \leq j < k \leq c_i$)。

输出

如果$T$不能是一棵树，则输出-1；否则，按照以下格式输出满足条件的$(u_i,v_i)$的选择：

$u_1$ $v_1$ $:$ $u_{N-1}$ $v_{N-1}$

样例输入 1

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

样例输出 1

1 2
1 3
3 4
4 5

样例输入 2

6
3 1 2 3
3 2 3 4
3 1 3 4
3 1 2 4
3 4 5 6

样例输出 2

-1

样例输入 3

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

样例输出 3

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