问题描述

给定一个具有$N$个顶点和$M$条边的无向图$G$。$G$是简单的（没有自环和多条边）且连通的。

对于$i=1,2,\ldots,M$，第$i$条边是连接顶点$u_i$和$v_i$的无向边$\lbrace u_i, v_i \rbrace$。

构造两个满足以下两个条件的图$G$的生成树$T_1$和$T_2$。（$T_1$和$T_2$不一定要是不同的生成树。）

• $T_1$满足以下条件。

  如果我们将$T_1$视为以顶点$1$为根的树，则对于$G$中不包含在$T_1$中的任意边$\lbrace u, v \rbrace$，$u$和$v$中的一个是另一个在$T_1$中的祖先。

• $T_2$满足以下条件。

  如果我们将$T_2$视为以顶点$1$为根的树，则$G$中不存在不包含在$T_2$中的边$\lbrace u, v \rbrace$，使得$u$和$v$中的一个是另一个在$T_2$中的祖先。

我们可以证明总是存在满足上述条件的$T_1$和$T_2$。

约束条件

• $2 \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq \min\lbrace 2 \times 10^5, N(N-1)/2 \rbrace$
• $1 \leq u_i, v_i \leq N$
• 输入中的所有值均为整数。
• 给定的图是简单且连通的。

输入

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

$N$ $M$ $u_1$ $v_1$ $u_2$ $v_2$ $\vdots$ $u_M$ $v_M$

输出

按以下格式打印$(2N-2)$行，以输出$T_1$和$T_2$。具体地说，

• 第$1$到第$(N-1)$行应包含$T_1$中包含的$(N-1)$个无向边$\lbrace x_1, y_1 \rbrace, \lbrace x_2, y_2 \rbrace, \ldots, \lbrace x_{N-1}, y_{N-1} \rbrace$，每行一条边。
• 第$N$到第$(2N-2)$行应包含$T_2$中包含的$(N-1)$个无向边$\lbrace z_1, w_1 \rbrace, \lbrace z_2, w_2 \rbrace, \ldots, \lbrace z_{N-1}, w_{N-1} \rbrace$，每行一条边。

可以按任意顺序打印每个生成树中的边。此外，可以以任意顺序打印每条边的端点。

$x_1$ $y_1$ $x_2$ $y_2$ $\vdots$ $x_{N-1}$ $y_{N-1}$ $z_1$ $w_1$ $z_2$ $w_2$ $\vdots$ $z_{N-1}$ $w_{N-1}$

示例输入1

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

示例输出1

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

上述示例输出中，$T_1$是包含$5$条边$\lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace$的$G$的生成树。$T_1$满足问题陈述中的条件。事实上，对于$G$中不包含在$T_1$中的每条边：

• 对于边$\lbrace 5, 1 \rbrace$，顶点$1$是$5$的祖先；
• 对于边$\lbrace 1, 2 \rbrace$，顶点$1$是$2$的祖先；
• 对于边$\lbrace 1, 6 \rbrace$，顶点$1$是$6$的祖先。

$T_2$是包含$5$条边$\lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace$的$G$的另一个生成树。$T_2$满足问题陈述中的条件。事实上，对于$G$中不包含在$T_2$中的每条边：

• 对于边$\lbrace 4, 3 \rbrace$，顶点$4$不是顶点$3$的祖先，反之亦然；
• 对于边$\lbrace 2, 6 \rbrace$，顶点$2$不是顶点$6$的祖先，反之亦然；
• 对于边$\lbrace 4, 2 \rbrace$，顶点$4$不是顶点$2$的祖先，反之亦然。

示例输入2

4 3
3 1
1 2
1 4

示例输出2

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

树$T$是$G$的唯一生成树，包含$3$条边$\lbrace 1, 2 \rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace$。由于$T$中包含$G$的所有边，显然$T$满足$T_1$和$T_2$的条件。