AT_abc251_f Two Spanning Trees

给定一个有 $N$ 个顶点和 $M$ 条边的无向图 $G$。$G$ 是简单图（即无自环和无重边）且连通的。 对于 $i = 1,2,\dots,M$，第 $i$ 条边是顶点 $u_i$ 和顶点 $v_i$ 和无向边边 $u_i\Leftrightarrow v_i$。 图 $G$ 的两棵全局树 $T_1$ 和 $T_2$，同时满足以下两个条件（$T_1$ 和 $T_2$ 可以相同）。 - $T_1$ 满足以下条件： > $T_1$ 是一棵以顶点 1 为根的有根树，对于原图 $G$ 上的两点 $u$ 和 $v$ 有 $u\Leftrightarrow v$，若这条边不是生成树中的树边，那么在生成树上这两点一定是祖先关系。 - $T_2$ 满足以下条件： > $T_2$ 是一棵以顶点 1 为根的有根树，对于原图 $G$ 上的两点 $u$ 和 $v$ 有 $u\Leftrightarrow v$，若这条边不是生成树中的树边，那么在生成树上这两点一定不是祖先关系。

第一行输入两个正整数 $N$ 和 $M$。 第 $2$ 行到第 $M+1$ 行每行输入两个整数，表示在原图 $G$ 上有这条无向边。

对于 $T_1$，输出从第 $1$ 行到第 $N-1$ 行，表示在满足 $T_1$ 生成条件下任意一棵生成树的所有边。 对于 $T_2$，输出从第 $2$ 行到第 $2N-2$ 行，表示在满足 $T_2$ 生成条件下任意一棵生成树的所有边。 注意：输出边的两个顶点顺序以及输出边的顺序都是任意的。

### 范围 - $2\le N\le 2\times 10^5$ - $N-1\le M \le \min \{ 2\times 10^5,\frac {N(N-1)}{2} \}$ - $1\le u_i,v_i\le N$ - 所有输入均为整数 - 给出的图简单且连通 ### 样例解释 1 在上述输出示例中，$T_1$ 是具有 5 条边 $\{ \{ 1, 4 \}, \{ 4, 3 \}, \{ 5, 3 \}, \{ 4, 2 \}, \{ 6, 2 \} \}$ 的图 $G$ 的一棵生成树。 这棵 $T_1$ 满足问题描述中的条件。实际上，对于图 $G$ 中不在 $T_1$ 里的每条边： -对于边 $\{ 5, 1 \}$，顶点 1 是顶点 5 的祖先； -对于边 $\{ 1, 2 \}$，顶点 1 是顶点 2 的祖先； -对于边 $\{ 1, 6 \}$，顶点 1 是顶点 6 的祖先。 $T_2$ 是具有 5 条边 $\{ \{ 1, 5 \}, \{ 5, 3 \}, \{ 1, 4 \}, \{ 2, 1 \}, \{ 1, 6 \} \}$ 的图 $G$ 的一棵生成树。 这棵 $T_2$ 满足问题描述中的条件。对于图 $G$ 中不在 $T_2$ 里的每条边： - 对于边 $\{ 4, 3 \}$，顶点 4 和顶点 3 不存在祖先——子孙关系； - 对于边 $\{ 2, 6 \}$，顶点 2 和顶点 6 不存在祖先——子孙关系； - 对于边 $\{ 4, 2 \}$，顶点 4 和顶点 2 不存在祖先——子孙关系。 ### 样例解释 2} 具有 3 条边 $\{ \{ 1, 2 \}, \{ 1, 3 \}, \{ 1, 4 \} \}$ 的树 $T$ 是图 $G$ 的唯一生成树。由于图 $G$ 中不存在不在这棵树 $T$ 里的边，显然，$T$ 同时满足 $T_1$ 和 $T_2$ 的条件。