102515: [AtCoder]ABC251 F - Two Spanning Trees

Memory Limit:256 MB Time Limit:2 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

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$.

Input

题意翻译

给定无向连通简单图,求其两个以 $ 1 $ 为根的生成树 $ T_1, T_2 $,满足: * 对于 $ T_1 $,其任意一条非树边连结的两个节点均存在祖先关系,即一个点为另一个点的祖先。 * 对于 $ T_2 $,其任意一条非树边连结的两个节点均不存在祖先关系。

Output

得分:500分

问题描述

你得到了一个有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$

输出

按照以下格式输出$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$,每行一条边。
  • 第$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}$		  

加入题单

上一题 下一题 算法标签: