F - Two Spanning Trees

Contest Duration: 2022-05-14 21:00:00+0900 - 2022-05-14 22:40:00+0900 (local time) (100 minutes) Back to Home

F - Two Spanning Trees Editorial

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 500 点

問題文

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 は必ず存在することが示せます。

制約

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

出力

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

出力例 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 は祖先と子孫の関係にありません。

入力例 2

出力例 2

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

Score : 500 points

Problem Statement

You are given an undirected graph G with N vertices and M edges. G is simple (it has no self-loops and multiple edges) and connected.

For i = 1, 2, \ldots, M, the i-th edge is an undirected edge \lbrace u_i, v_i \rbrace connecting Vertices u_i and v_i.

Construct two spanning trees T_1 and T_2 of G that satisfy both of the two conditions below. (T_1 and T_2 do not necessarily have to be different spanning trees.)

T_1 satisfies the following.

If we regard T_1 as a rooted tree rooted at Vertex 1, for any edge \lbrace u, v \rbrace of G not contained in T_1, one of u and v is an ancestor of the other in T_1.
T_2 satisfies the following.

If we regard T_2 as a rooted tree rooted at Vertex 1, there is no edge \lbrace u, v \rbrace of G not contained in T_2 such that one of u and v is an ancestor of the other in T_2.

We can show that there always exists T_1 and T_2 that satisfy the conditions above.

Constraints

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
All values in input are integers.
The given graph is simple and connected.

Input

Input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
\vdots
u_M v_M

Output

Print (2N-2) lines to output T_1 and T_2 in the following format. Specifically,

The 1-st through (N-1)-th lines should contain the (N-1) undirected edges \lbrace x_1, y_1\rbrace, \lbrace x_2, y_2\rbrace, \ldots, \lbrace x_{N-1}, y_{N-1}\rbrace contained in T_1, one edge in each line.
The N-th through (2N-2)-th lines should contain the (N-1) undirected edges \lbrace z_1, w_1\rbrace, \lbrace z_2, w_2\rbrace, \ldots, \lbrace z_{N-1}, w_{N-1}\rbrace contained in T_2, one edge in each line.

You may print edges in each spanning tree in any order. Also, you may print the endpoints of each edge in any order.

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}

Sample Input 1

Sample Output 1

In the Sample Output above, T_1 is a spanning tree of G containing 5 edges \lbrace 1, 4 \rbrace, \lbrace 4, 3 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 4, 2 \rbrace, \lbrace 6, 2 \rbrace. This T_1 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_1:

for edge \lbrace 5, 1 \rbrace, Vertex 1 is an ancestor of 5;
for edge \lbrace 1, 2 \rbrace, Vertex 1 is an ancestor of 2;
for edge \lbrace 1, 6 \rbrace, Vertex 1 is an ancestor of 6.

T_2 is another spanning tree of G containing 5 edges \lbrace 1, 5 \rbrace, \lbrace 5, 3 \rbrace, \lbrace 1, 4 \rbrace, \lbrace 2, 1 \rbrace, \lbrace 1, 6 \rbrace. This T_2 satisfies the condition in the Problem Statement. Indeed, for each edge of G not contained in T_2:

for edge \lbrace 4, 3 \rbrace, Vertex 4 is not an ancestor of Vertex 3, and vice versa;
for edge \lbrace 2, 6 \rbrace, Vertex 2 is not an ancestor of Vertex 6, and vice versa;
for edge \lbrace 4, 2 \rbrace, Vertex 4 is not an ancestor of Vertex 2, and vice versa.

Sample Input 2

Sample Output 2

Tree T, containing 3 edges \lbrace 1, 2\rbrace, \lbrace 1, 3 \rbrace, \lbrace 1, 4 \rbrace, is the only spanning tree of G. Since there are no edges of G that are not contained in T, obviously this T satisfies the conditions for both T_1 and T_2.