結論を述べると、\(T_1\) として頂点 \(1\) を根とする \(G\) の深さ優先探索（DFS）木を、\(T_2\) として頂点 \(1\) を根とする \(G\) の幅優先探索（BFS）木を出力すれば、この問題に正解できます。

[1] DFS 木とは

（頂点 \(1\) を根とする）DFS 木とは、頂点 \(1\) からはじめて（同じ頂点を \(2\) 度以上訪れないように）深さ優先探索を行うとき、その過程で通る辺からなる木です。

次の図に入力例１のグラフ \(G\) に対する DFS 木の例を赤太線で示します。

この DFS 木 \(T_1\) を作る DFS の過程の例を次に述べます。

• まず、頂点 \(1\) からはじめ、未訪問の頂点 \(2\) に移動します。このときに通る辺 \(\lbrace 1, 2 \rbrace\) を \(T_1\) に追加します。
• 頂点 \(2\) から、未訪問の頂点 \(6\) に移動します。このときに通る辺 \(\lbrace 2, 6 \rbrace\) を \(T_1\) に追加します。
• 未訪問の頂点がこれ以上先に存在しないため、頂点 \(6\) から頂点 \(2\) に戻ります。
• 次に、頂点 \(2\) から、未訪問の頂点 \(4\) に移動します。このときに通る辺 \(\lbrace 2, 4 \rbrace\) を \(T_1\) に追加します。
• 頂点 \(4\) から、未訪問の頂点 \(3\) に移動します。このときに通る辺 \(\lbrace 4, 3 \rbrace\) を \(T_1\) に追加します。
• 頂点 \(3\) から、未訪問の頂点 \(5\) に移動します。このときに通る辺 \(\lbrace 3, 5 \rbrace\) を \(T_1\) に追加します。
• 未訪問の頂点がこれ以上先に存在しないため、頂点 \(5\) から頂点 \(3\) に、頂点 \(3\) から頂点 \(4\) に、頂点 \(4\) から頂点 \(2\) に、さらに頂点 \(2\) から頂点 \(1\) に戻り、DFS が終了します。

一般に、DFS 木は唯一とは限らないことに注意してください。DFS の過程で次に到達できる未訪問の頂点が複数ある場合にどれを選ぶかによって、最終的に出来上がる DFS 木は異なります。

\(G\) のDFS 木 \(T_1\) は「 \(T_1\) に含まれないすべての \(G\) の辺 \(\lbrace u, v\rbrace\) について \(u\) と \(v\) が祖先と子孫の関係にある」という性質を持ちます。 これは、もし \(T_1\) に含まれない \(G\) の辺 \(\lbrace u, v \rbrace\) で \(u\) と \(v\) が祖先と子孫の関係にないものが存在すると、深さ優先探索の「行く先に未訪問の頂点がある限り進む」という定義に矛盾することから解ります。

[2] BFS 木とは

（頂点 \(1\) を根とする）BFS 木とは、頂点 \(1\) からはじめて（同じ頂点を \(2\) 度以上訪れないように）幅優先探索を行うとき、その過程で通る辺からなる木です。

次の図に入力例１のグラフ \(G\) に対する BFS 木の例を青太線で示します。

この BFS 木 \(T_2\) を作るBFSの過程の例を次に述べます。

• まず、頂点 \(1\) をキューに入れた状態から始めます。
• キューの先頭から頂点 \(1\) を取り出し、頂点 \(1\) に隣接する未訪問の頂点である、頂点 \(5\) 、頂点 \(2\) 、頂点 \(4\) 、頂点 \(6\) を訪問（キューの末尾に追加）します。このときに通る辺 \(\lbrace 1, 5\rbrace, \lbrace 1, 4\rbrace, \lbrace 1, 2\rbrace, \lbrace 1, 6\rbrace\) をそれぞれ \(T_2\) に追加します。
• キューの先頭から頂点 \(5\) を取り出し、頂点 \(5\) に隣接する未訪問の頂点である頂点 \(3\) を訪問（キューの末尾に追加）します。このときに通る辺 \(\lbrace 5, 3\rbrace\) を \(T_2\)に追加します。
• その後、キューの先頭から頂点 \(4\) 、頂点 \(2\) 、頂点 \(6\) 、頂点 \(3\) が順に取り出されますが、未訪問の頂点はもう存在しないためこのまま BFS が終了します。

DFS 木と同様に、BFS 木も一般に唯一とは限りません。

\(G\) が単純グラフである本問題の制約下では、\(G\) の BFS 木 \(T_2\) は 「 \(T_2\) に含まれないどの \(G\) の辺 \(\lbrace u, v\rbrace\) についても \(u\) と \(v\) は祖先と子孫の関係にはない」という性質を持ちます。 このことを以下で示します。

\(T_2\) に含まれない \(G\) のある辺 \(e = \lbrace u, v\rbrace\) について、\(u\) が \(v\) の祖先であったと仮定して矛盾を導きます。 BFS 木の作られ方から、頂点 \(1\) から各頂点への \(G\) 上での最短距離は、頂点 \(1\) から各頂点への \(T_2\) 上での最短距離と等しいです。 そこで、\(u, v\) の頂点 \(1\) からの（ \(G\) 上および \(T_2\) 上での）最短距離をそれぞれ \(d(u), d(v)\) とおきます。 \(u\) は \(v\) の先祖であり、また \(G\) は自己ループを持たないことから、\(d(u)+1 \leq d(v)\) です。 さらに、\(u\) と \(v\) を結ぶ辺 \(e\) が存在することから、\(d(u)+1 \geq d(v)\) です。 よって、\(d(u) +1 = d(v)\) ですが、これは \(u\) が \(T_2\) 上で \(v\) の直接の親であることを意味するため、\(T_2\) 上にも \(u\) と \(v\) を結ぶ辺 \(e'\) が存在することになります。 \(e\) と \(e'\) は多重辺をなすため、\(G\) が単純であるという本問題の制約に矛盾します。 以上で「 \(T_2\) に含まれないどの \(G\) の辺 \(\lbrace u, v\rbrace\) についても \(u\) と \(v\) は祖先と子孫の関係にはない」ことが示されました。

一般に、競技プログラミング等の問題を解く上で、与えられたグラフの適当な全域木を求める必要がしばしば生じます。その際に、上に述べた DFS 木や BFS 木を用いることができます。 また、DFS 木の「 DFS 木に含まれないすべての辺 \(\lbrace u, v\rbrace\) について \(u\) と \(v\) が祖先と子孫の関係にある」という性質が問題を解く上で重要となることもあります。

本問題の C++ 言語による正解例を以下に記載します。

#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;
}