#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define MAX(a, b) (a) = max((a), (b))
#define MIN(a, b) (a) = min((a), (b))
#define all(a) (a).begin(), (a).end()
#define sortedpair(a, b) {min((a), (b)), max((a), (b))}

const ll MOD = 1e9+7;

const int MAXN = 100'001;

struct E {
    int u, v, w;

    E(int a, int b, int c) : u(a), v(b), w(c) {}
};

int ans[MAXN];
vector<int> g[MAXN];

void solve(){
    int n, m; cin>>n>>m;
    vector<pair<int, int>> edges;
    for (int i = 0; i < m; i++) {
        int u, v; cin >> u >> v;
        edges.emplace_back(u, v);
    }
    while (true) {
        for (int i = 1; i <= n; i++) {
            ans[i] = rand()&1;
        }
        int ok = 0;
        for (auto [u, v] : edges) {
            if (ans[u] == ans[v]) ok++;
        }
        if (ok <= m/2) {
            break;
        }
    }
    cout << count(ans+1, ans+n+1, 1) << "\n";
    for (int i = 1; i <= n; i++) {
        if (ans[i]) cout << i << " ";
    }
    cout << "\n";
}

int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int _t = 1;
    cin >> _t;
    while (_t--) {
        solve();
    }
    return 0;
}