题目描述

$N$ 頂点 $M$ 辺の無向グラフ $G$ が与えられます。 $G$ は単純（自己ループおよび多重辺を持たない）かつ連結です。

$i\ =\ 1,\ 2,\ \ldots,\ M$ について、$i$ 番目の辺は頂点 $u_i$ と頂点 $v_i$ を結ぶ無向辺 $\lbrace\ u_i,\ v_i\ \rbrace$ です。

下記の $2$ つの条件をともに満たすような $G$ の $2$ つの全域木 $T_1,T_2$ を $1$ 組構成してください。（ $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$ において頂点 $u$ と頂点 $v$ が祖先と子孫の関係にある」とは、「 $T$ において $u$ が $v$ の祖先である」と「 $T$ において $v$ が $u$ の祖先である」のうちどちらかが成り立つことをいいます。

本問題の制約下において上記の条件を満たす $T_1$ と $T_2$ は必ず存在することが示せます。

输入格式

入力は以下の形式で標準入力から与えられます。

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

输出格式

$T_1$ と $T_2$ を下記の形式にしたがって、$2N-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 $ を、各行に $1$ 本ずつ出力してください。
• $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 $ を、各行に $1$ 本ずつ出力してください。

各全域木を構成する辺をどのような順番で出力するかや、各辺の出力においてどちらの端点を先に出力するかは任意です。

$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$ 为根的生成树 $T_1, T_2$，满足：

• 对于 $T_1$，其任意一条非树边连结的两个节点均存在祖先关系，即一个点为另一个点的祖先。
• 对于 $T_2$，其任意一条非树边连结的两个节点均不存在祖先关系。

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

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

4 3
3 1
1 2
1 4

1 2
1 3
1 4
1 4
1 3
1 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$
• 入力はすべて整数
• 与えられるグラフは単純かつ連結

Sample Explanation 1

上記の出力例において、$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$ は祖先と子孫の関係にありません。

Sample Explanation 2

$3$ 本の辺 $ \lbrace\ 1,\ 2\rbrace,\ \lbrace\ 1,\ 3\ \rbrace,\ \lbrace\ 1,\ 4\ \rbrace $ を持つ木 $T$ が $G$ の唯一の全域木です。 $G$ の辺のうちこの木 $T$ に含まれない辺は存在しないので、明らかに、$T$ は $T_1$ の条件と $T_2$ の条件をともに満たします。