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
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
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
6 8 5 1 4 3 1 4 3 5 1 2 2 6 1 6 4 2
Sample Output 1
1 4 4 3 5 3 4 2 6 2 1 5 5 3 1 4 2 1 1 6
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
4 3 3 1 1 2 1 4
Sample Output 2
1 2 1 3 1 4 1 4 1 3 1 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.