WASTE THUIS/*
ID: ashish1610
PROG:
LANG: C++
*/
#include<algorithm>
#include<iostream>
#include<vector>
#include<cstring>
using namespace std;
#define ll  long long int
#define MOD 1000000007
vector<int> adj[1000005];
vector<pair<int,int> > adj1[1000005];
bool visited[1000005]={false};
void dfs(int nd)
{
    visited[nd]=true;
    cout<<nd<<" ";
    for(int i=0;i<adj[nd].size();++i)
    {
        int tmp=adj[nd][i];
        if(!visited[tmp])
            dfs(tmp);
    }
}
void bfs(int nd)
{
    queue<int> q;
    q.push(nd);
    while(!q.empty())
    {
        int nd=q.front();
        q.pop();
        cout<<nd<<" ";
        visited[nd]=true;
        for(int i=0;i<adj[nd].size();++i)
        {
            int tmp=adj[nd][i];
            if(!visited[tmp])
                q.push(adj[nd][i]);
        }
    }
}
int main()
{
    int t;
    cin>>t;
    while(t--)
    {
        for(int i=0;i<100005;++i)
            adj[i].clear();
        int n,m,x,y;//n no. of nodes, m edges
        cin>>n>>m;
        /*

            If graph is this :


                2
               / \
              1   3
             / \
            4   5

            Than input will be :
            5 4 // 5 : no of nodes, 4 : no of edges
            //these 4 are edges of graph above
            2 3
            2 1
            1 4
            1 5

        */
        for(int i=0;i<m;++i)
        {
            cin>>x>>y;
            adj[x].push_back(y);
            adj[y].push_back(x);
            /*.................*/
            /* if edges have weights */
            /*cin>>x>>y>>w;
            adj1[x].push_back(make_pair(y,w));
            adj1[y].push_back(make_pair(x,w));*/
        }
        memset(visited,false,sizeof(visited)); // to set the complete visited array as false.
        cout<<"DFS traversal\n";
        dfs(1);
        cout<<endl;
        cout<<"BFS traversal\n";
        bfs(1);
        cout<<endl;
    }
    return 0;
}