题目描述
N 頂点 M 辺の無向グラフ G が与えられます。 G は単純(自己ループおよび多重辺を持たない)かつ連結です。
i = 1, 2, …, M について、i 番目の辺は頂点 ui と頂点 vi を結ぶ無向辺 { ui, vi } です。
下記の 2 つの条件をともに満たすような G の 2 つの全域木 T1,T2 を 1 組構成してください。( T1 と T2 は異なる全域木である必要はありません。)
-
T1 は下記を満たす。
T1 を頂点 1 を根とする根付き木とみなしたとき、G の辺のうち T1 に含まれないすべての辺 { u, v } について、u と v は T1 において祖先と子孫の関係にある。
-
T2 は下記を満たす。
T2 を頂点 1 を根とする根付き木とみなしたとき、G の辺のうち T2 に含まれない辺 { u, v } であって、u と v が T2 において祖先と子孫の関係にあるようなものは存在しない。
ここで、「根付き木 T において頂点 u と頂点 v が祖先と子孫の関係にある」とは、「 T において u が v の祖先である」と「 T において v が u の祖先である」のうちどちらかが成り立つことをいいます。
本問題の制約下において上記の条件を満たす T1 と T2 は必ず存在することが示せます。
输入格式
入力は以下の形式で標準入力から与えられます。
N M u1 v1 u2 v2 ⋮ uM vM
输出格式
T1 と T2 を下記の形式にしたがって、2N−2 行にわたって出力してください。すなわち、
- 1 行目から N−1 行目には、T1 に含まれる N−1 本の無向辺 { x1, y1}, { x2, y2}, …, { xN−1, yN−1} を、各行に 1 本ずつ出力してください。
- N 行目から 2N−2 行目には、T2 に含まれる N−1 本の無向辺 { z1, w1}, { z2, w2}, …, { zN−1, wN−1} を、各行に 1 本ずつ出力してください。
各全域木を構成する辺をどのような順番で出力するかや、各辺の出力においてどちらの端点を先に出力するかは任意です。
x1 y1 x2 y2 ⋮ xN−1 yN−1 z1 w1 z2 w2 ⋮ zN−1 wN−1
题目大意
给定无向连通简单图,求其两个以 1 为根的生成树 T1,T2,满足:
- 对于 T1,其任意一条非树边连结的两个节点均存在祖先关系,即一个点为另一个点的祖先。
- 对于 T2,其任意一条非树边连结的两个节点均不存在祖先关系。
提示
制約
- 2 ≤ N ≤ 2 × 105
- N−1 ≤ M ≤ min{ 2 × 105, N(N−1)/2 }
- 1 ≤ ui, vi ≤ N
- 入力はすべて整数
- 与えられるグラフは単純かつ連結
Sample Explanation 1
上記の出力例において、T1 は 5 本の辺 { 1, 4 }, { 4, 3 }, { 5, 3 }, { 4, 2 }, { 6, 2 } を持つ G の全域木です。この T1 は問題文中の条件を満たします。実際、G の辺のうち T1 に含まれない各辺に関して、 - 辺 { 5, 1 } について、頂点 1 は頂点 5 の祖先であり、 - 辺 { 1, 2 } について、頂点 1 は頂点 2 の祖先であり、 - 辺 { 1, 6 } について、頂点 1 は頂点 6 の祖先です。 また、T2 は 5 本の辺 { 1, 5 }, { 5, 3 }, { 1, 4 }, { 2, 1 }, { 1, 6 } を持つ G の全域木です。この T2 は問題文中の条件を満たします。実際、G の辺のうち T2 に含まれない各辺に関して、 - 辺 { 4, 3 } について、頂点 4 と頂点 3 は祖先と子孫の関係になく、 - 辺 { 2, 6 } について、頂点 2 と頂点 6 は祖先と子孫の関係になく、 - 辺 { 4, 2 } について、頂点 4 と頂点 2 は祖先と子孫の関係にありません。
Sample Explanation 2
3 本の辺 { 1, 2}, { 1, 3 }, { 1, 4 } を持つ木 T が G の唯一の全域木です。 G の辺のうちこの木 T に含まれない辺は存在しないので、明らかに、T は T1 の条件と T2 の条件をともに満たします。