#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define F0R(i,a) for(int i=0; i<a; i++)
#define FOR(i,a,b) for(int i=a; i<=b; i++)
#define pb push_back
#define f first
#define s second

#define MN 200005
int n, m;
vi e[MN];
pii d[MN];
int p[MN];
bool on[MN];

void dfs(int cn){
    for(auto nn : e[cn]) if(nn != p[cn] && p[nn] == -1){
        p[nn] = cn;
        d[nn].f = d[cn].f+1;
        dfs(nn);
    }
}
int main(){
    memset(p, -1, sizeof p);
    int t;
    cin >> t;
    F0R(summit, t){
        cin >> n >> m;
        int rt = 0;
        while(rt*rt<n) rt++;
        F0R(_, m){
            int u, v;
            cin >> u >> v;
            e[u].pb(v);
            e[v].pb(u);
        }
        FOR(i, 1, n){
            d[i].s = i;
        }
        p[1] = 0; 
        dfs(1);
        sort(d+1, d+n+1);
        vi used;
        for(int i=n; i>=1; i--){
            int cur = d[i].s;
            bool ok = false;
            F0R(_, rt){
                if(on[cur]){ ok = true; break; }
                if(cur==1) break;
                cur = p[cur];
            }
            if(!ok){
                on[cur]=true;
                used.pb(cur);
            }
        }

        if (used.size() > rt){
          cout << n << " " << m << endl;
          FOR(i, 1, n){
            for(int j : e[i]){
              if (i < j)
              cout << i << " " << j << endl;
            }
          }
        }

        if (t <= 10){
        cout << used.size() << "\n";
        for(auto u : used) cout << u << " ";
        cout << "\n";
        }
        FOR(i, 1, n){
            e[i].clear();
            d[i] = {0, 0};
            p[i] = -1;
            on[i] = false;
        }

        F0R(i, 100){
          assert (e[i].size() == 0);
          assert (d[i].s == 0);
          assert (d[i].f == 0);
          assert (p[i] == -1);
          assert (! on[i]);

        }
    }
    return 0;
}