To come to the point, we can output a Depth-First Search (DFS) Tree rooted at Vertex \(1\) as \(T_1\), and a Breadth-First Search (BFS) Tree rooted at Vertex \(1\) as \(T_2\) in order to be accepted.

[1] What is DFS tree?

A DFS tree (rooted at Vertex \(1\)) is a tree consisting of edges that are walked through when performing Depth-First Search starting from Vertex \(1\) (so that no vertex is visited more than once).

The following is an example of a DFS tree of Graph \(G\) given in Sample Input \(1\).

Here is the process in which the DFS tree \(T_1\) is built.

• Starting from Vertex \(1\), first travel to unvisited Vertex \(2\). Add the edge we walk through, \(\lbrace 1, 2 \rbrace\) to \(T_1\).
• From Vertex \(2\), travel to unvisited Vertex \(6\). Add the edge we walk through, \(\lbrace 2, 6 \rbrace\), to \(T_1\).
• We have no more edge that has been visited, so go back from Vertex \(6\) to Vertex \(2\).
• Next, from Vertex \(2\), travel to unvisited Vertex \(4\). Add the edge we walk through, \(\lbrace 2, 4 \rbrace\), to the tree.
• From Vertex \(4\), travel to unvisited Vertex \(3\). Add the edge we walk through, \(\lbrace 4, 3 \rbrace\), to the tree.
• From Vertex \(3\), travel to unvisited Vertex \(5\). Add the edge we walk through, \(\lbrace 3, 5 \rbrace\), to the tree.
• We don’t have any unvisited vertex anymore, so we go back from Vertex \(5\) to Vertex \(3\), from Vertex \(3\) to Vertex \(4\), from Vertex \(4\) to Vertex \(2\), and from Vertex \(2\) to Vertex \(1\); then we terminate the DFS.

Note that a DFS tree is not necessarily unique in general. Depending on the choice of unvisited vertices during the DFS, the resulting DFS may vary too.

The DFS tree \(T_1\) of \(G\) has the property that “for every edge \(\lbrace u, v\rbrace\) of \(G\) not contained in \(T_1\), one of \(u\) and \(v\) is an ancestor of another.” This is because, if there exists an edge \(\lbrace u, v\rbrace\) of \(G\) not contained in \(T_1\) such that \(u\) is not an ancestor of \(v\) and vice versa, it contradicts the property of DFS that “it advances as long as there is an unvisited vertex around the current vertex.”

[2] What is BFS tree?

A BFS tree (rooted at Vertex \(1\)) is a tree consisting of edges that are walked through when performing Breadth-First Search starting from Vertex \(1\) (so that no vertex is visited more than once).

Here is an example of a BFS tree of Graph \(G\) given in Sample Input \(1\).

• We start with a state where a queue contains only Vertex \(1\).
• We pop Vertex \(1\) from the queue and visit (push to the tail of the queue) Vertices \(5, 2, 4\), and \(6\), which are unvisited vertices adjacent to Vertex \(1\), while adding edges \(\lbrace 1, 5\rbrace, \lbrace 1, 4\rbrace, \lbrace 1, 2\rbrace\) and \(\lbrace 1, 6\rbrace\) to \(T_2\).
• We pop Vertex \(5\) from the queue and visit (push to the tail of the queue) Vertex \(3\), which is an unvisited vertex adjacent to Vertex \(3\), while adding edge \(\lbrace 5, 3\rbrace\) to \(T_2\).
• Then, Vertices \(4\), \(2\), \(6\), and \(3\) are popped from the head of the queue in this order, but we no longer have unvisited vertices, so the BFS is immediately terminated.

Just like DFS trees, BFS trees are not unique either.

Under the Constraints of this problem that \(G\) is a simple graph, a BFS tree \(T_2\) of \(G\) has the property that “for any edge \(\lbrace u, v\rbrace\) of \(G\) not contained in \(T_2\), \(u\) is not an ancestor of \(v\), and vice versa.” We will justify the fact.

We suppose that there exists an edge \(e = \lbrace u, v\rbrace\) of \(G\) not contained in \(T_2\) such that \(u\) is an ancestor of \(v\). By the construction of the BFS tree, the shortest distance from Vertex \(1\) to each vertex on \(G\) is equal to that from Vertex \(1\) to each vertex on \(T_2\). Let \(d(u)\) and \(d(v)\) be the shortest distances from Vertex \(1\) to Vertices \(u\) and \(v\) (on \(G\) and \(T_2\)), respectively. Since \(u\) is an ancestor of \(v\) and \(G\) does not have a self-loop, \(d(u)+1 \leq d(v)\). Moreover, since there exists an edge \(e\) that connects \(u\) and \(v\), we have \(d(u)+1 \geq d(v)\). Therefore, \(d(u) +1 = d(v)\), which means that \(u\) is a direct parent of \(v\) on \(T_2\), and thus \(T_2\) has an edge \(e'\) that directly connects \(u\) and \(v\). Since \(e\) and \(e'\) are multiple edges, it contradicts to the Constraint of the problem that \(G\) is simple. Therefore, we have shown that “for any edge \(\lbrace u, v\rbrace\) of \(G\) not contained in \(T_2\), \(u\) is not an ancestor of \(v\), and vice versa.”

In general, when solving problems of competitive programming, we often need to find some spanning trees of the given graph. We may use DFS trees and BFS trees for that purpose. Also, the property of DFS trees that “for every edge \(\lbrace u, v\rbrace\) of \(G\) not contained in \(T_1\), one of \(u\) and \(v\) is an ancestor of another,” which is sometimes important for solving problems.

The following is a sample accepted code for this problem in C++ language.

#include <iostream>
#include <utility>
#include <queue>
using namespace std;
typedef long long ll;
typedef pair<int, int> P;
const ll inf = 1e18;

int n, m;
vector<int> G[200005];
bool visited[200005];
vector<P> T1, T2;

void dfs(int v)
{
  visited[v] = true;
  for(auto u : G[v]){
    if(!visited[u]){
      T1.push_back(P(v, u));
      dfs(u);
    }
  }
}
void bfs()
{
  for(int i = 1; i <= n; i++) visited[i] = false;
  queue<int> Q;
  Q.push(1), visited[1] = true;
  
  int v;
  while(Q.size()){
    v = Q.front(), Q.pop();
    for(auto u : G[v]){
      if(!visited[u]){
        T2.push_back(P(v, u));
        visited[u] = true;
        Q.push(u);
      }
    }
  }
}

int main(void)
{
  cin >> n >> m;
  int u, v;
  for(int i = 1; i <= m; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  
  dfs(1);
  bfs();
  
  for(auto p : T1) cout << p.first << " " << p.second << "\n";
  for(auto p : T2) cout << p.first << " " << p.second << "\n";
  
  return 0;
}