// UUID: 2510d2b3-93f2-46aa-be95-008e9b2e04ce
#include <bits/stdc++.h>
using namespace std;

#define endl '\n'
#define pb push_back
#define iter(v) v.begin(), v.end()
#define riter(v) v.rbegin(), v.rend()
#define vi vector<int>
#define vvi vector<vector<int>>
//#define int long long

void solve() {
    srand(time(0));
    int n,m;cin>>n>>m;
    vector<array<int, 2>>ed(m+1);
    for(int i=1;i<=m;i++){
        cin>>ed[i][0]>>ed[i][1];
    }
    vi team(n+1);
    int tries=5;
    while(tries--){
        for(int i=1;i<=n;i++){
            team[i]=rand()%2;
        }
        int cost=0;
        for(int i=1;i<=m;i++){
            cost += (team[ed[i][0]] == team[ed[i][1]]);
        }
        if(cost<=m/2){
            int tot=0;
            for(int i:team)tot+=i;
            cout << tot<<endl;
            for(int i=1;i<=n;i++)if(team[i])cout<<i<<" ";
            cout << endl;
            return;
        }
    }
}

signed main() {
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    int t;cin>>t;
    while(t--)solve();
}