Score : $500$ points
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.
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$
Print $(2N-2)$ lines to output $T_1$ and $T_2$ in the following format. Specifically,
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}$
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
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$:
$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$:
4 3 3 1 1 2 1 4
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$.