AT_agc029_f.[AGC029F] Construction of a tree

给定 $N$ 个元素的集合 $\{1,2,\ldots,N\}$ 的 $N-1$ 个子集。第 $i$ 个集合记为 $E_i$。

你需要从每个集合 $E_i$ 中选择两个不同的元素 $u_i, v_i$，以 $\{1,2,\ldots,N\}$ 作为顶点集，$(u_1,v_1),(u_2,v_2),\ldots,(u_{N-1},v_{N-1})$ 作为边集，构造一个 $N$ 个顶点、$N-1$ 条边的图 $T$。请判断是否可以通过合理选择 $u_i, v_i$，使得 $T$ 是一棵树。如果可以，请给出一组实际的 $(u_1,v_1),(u_2,v_2),\ldots,(u_{N-1},v_{N-1})$ 使得 $T$ 是一棵树。

输入通过标准输入给出，格式如下：

$N$ $c_1$ $w_{1,1}$ $w_{1,2}$ $\ldots$ $w_{1,c_1}$ $:$ $c_2$ $w_{2,1}$ $w_{2,2}$ $\ldots$ $w_{2,c_2}$ $:$ $\ldots$ $:$ $c_{N-1}$ $w_{N-1,1}$ $w_{N-1,2}$ $\ldots$ $w_{N-1,c_{N-1}}$

其中，$c_i$ 表示 $E_i$ 的元素个数，$w_{i,1},\ldots,w_{i,c_i}$ 是 $E_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_1,v_1),(u_2,v_2),\ldots,(u_{N-1},v_{N-1})$，格式如下：

$u_1$ $v_1$ $:$ $u_2$ $v_2$ $:$ $\ldots$ $:$ $u_{N-1}$ $v_{N-1}$

限制条件

• $2 \leq N \leq 10^5$
• $E_i$ 是 $\{1,2,\ldots,N\}$ 的子集。
• $|E_i| \geq 2$
• 所有 $|E_i|$ 的总和不超过 $2 \times 10^5$。

由 ChatGPT 4.1 翻译