#include<bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
 
using namespace std;
using namespace __gnu_pbds;
typedef long long int lld;
typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;
#define rep(i,a,b) for(int i=a;i<b;i++)
#define trav(a,v) for(auto a:v)
#define pb push_back
#define all(a) a.begin(),a.end()
#define sz(a) (int)a.size()
// 1-based nodes; use -u to represent 'not u'
struct TwoSAT {
	int n;
	vector<int> adj[2000], radj[2000];
	vector<int> scc_id, topsort, answer;
	vector<bool> visited;
	TwoSAT() {}
	//TwoSAT(int _n) {
		//n = _n;
		//adj.resize(2*n+1), radj.resize(2*n+1);
		//scc_id.resize(2*n+1), answer.resize(2*n+1), visited.resize(2*n+1);
	//}
	void init(int _n){
		n = _n;
		//adj.clear();
		//radj.clear();
		rep(i,0,2*n+1)adj[i].clear(),radj[i].clear();
		scc_id.clear();
		answer.clear();
		visited.clear();
		//adj.resize(2*n+1), radj.resize(2*n+1);
		scc_id.resize(2*n+1), answer.resize(2*n+1), visited.resize(2*n+1);
	}
	void add_edge(int a, int b) {
		int not_a = a<0 ? -a : a+n;
		int not_b = b<0 ? -b : b+n;
		if (a<0) a=n-a;
		if (b<0) b=n-b;
		adj[a].pb(b);
		adj[not_b].pb(not_a);
		radj[b].pb(a);
		radj[not_a].pb(not_b);
	}
	void add_or(int a, int b) { add_edge(-a, b); }
	void add_xor(int a, int b) { add_or(a, b); add_or(-a, -b); }
	void add_imply(int a, int b) { add_edge(a, b); }
	void add_equivalent(int a, int b) { add_imply(a, b); add_imply(b, a); }
	void force_true(int a) { add_or(a, a); }
	void force_false(int a) { add_or(-a, -a); }
	void dfs(int u) {
		visited[u] = true;
		for (int v : adj[u]) if (!visited[v]) dfs(v);
		topsort.pb(u);
	}
	void rdfs(int u, int scc) {
		visited[u] = true;
		scc_id[u] = scc;
		for (int v : radj[u]) if (!visited[v]) rdfs(v, scc);
	}
	// Returns whether the formula is satisfiable and, if so, puts in 'answer' a satisfying assignment.
	bool solve() {
		fill(all(visited), false);
		for (int i = 1; i <= 2*n; i++) if (!visited[i]) dfs(i);
		reverse(all(topsort));
		fill(all(visited), false);
		int scc = 0;
		for (int u : topsort) if (!visited[u]) rdfs(u, scc++);
		for (int i = 1; i <= n; i++) {
			if (scc_id[i] == scc_id[i+n]) return false;
			answer[i] = scc_id[i] > scc_id[i+n];
		}
		return true;
	}
};

// General matching (Edmonds' blossom algorithm) in O(N^3).
struct Blossom {
	int n, m; // number of vertices and blossoms (not edges!)
	vector<int> mate, p, d, bl;
	vector<int> b[2000];
	int adj[2000][2000];
	//Blossom(int _n) {
		//n = _n, m = n + n/2; // m = 3n/2
		//mate.assign(n, -1);
		//b.resize(m), p.resize(m), d.resize(m), bl.resize(m);
		//adj.assign(m, vector<int>(m, -1));
	//}
	void init(int _n) {
		n = _n, m = n + n/2; // m = 3n/2
		mate.clear();
		p.clear();
		d.clear();
		bl.clear();
		rep(i,0,2*n){
			b[i].clear();
			rep(j,0,2*n)adj[i][j]=-1;
		}
		mate.assign(n, -1);
		p.resize(m), d.resize(m), bl.resize(m);
		//adj.assign(m, vector<int>(m, -1));
	}
	void add_edge(int u, int v) { adj[u][v] = u; adj[v][u] = v; }
	void match(int u, int v) { adj[u][v] = adj[v][u] = -1; mate[u]=v; mate[v]=u; }
	vector<int> trace(int x) {
		vector<int> vx;
		while (1) {
			while (x != bl[x]) x = bl[x];
			if (!vx.empty() && vx.back() == x) break;
			vx.push_back(x);
			x = p[x];
		}
		return vx;
	}
	void contract(int c, vector<int> &vx, vector<int> &vy) {
		b[c].clear();
		int r = vx.back();
		while (!vx.empty() && !vy.empty() && vx.back() == vy.back()) {
			r = vx.back(), vx.pop_back(), vy.pop_back();
		}
		b[c].push_back(r);
		b[c].insert(b[c].end(), vx.rbegin(), vx.rend());
		b[c].insert(b[c].end(), vy. begin(), vy. end());
		for (int i = 0; i <= c; i++) adj[c][i] = adj[i][c] = -1;
		for (int z : b[c]) {
			bl[z] = c;
			for (int i = 0; i < c; i++) if (adj[z][i] != -1) {
				adj[c][i] = z; adj[i][c] = adj[i][z];
			}
		}
	}
	vector<int> lift(vector<int> &vx) {
		vector<int> A;
		while (sz(vx) >= 2) {
			int z = vx.back(); vx.pop_back();
			if (z < n) { A.push_back(z); continue; }
			int w = vx.back();
			int i = int(~sz(A)&1 ? find(all(b[z]), adj[z][w])-b[z].begin():0);
			int j = int( sz(A)&1 ? find(all(b[z]), adj[z][A.back()])-b[z].begin():0);
			int k = sz(b[z]);
			int dif = (~sz(A)&1 ? i&1 : ~j&1) ? 1 : k-1;
			while (i != j) vx.push_back(b[z][i]), i = (i+dif)%k;
			vx.push_back(b[z][i]);
		}
		return A;
	}
	int solve() {
		for (int ans = 0; ; ans++) {
			fill(all(d), 0);
			queue<int> q;
			for (int i = 0; i < m; i++) bl[i] = i;
			for (int i = 0; i < n; i++) if (mate[i]==-1) q.push(i), p[i]=i, d[i]=1;
			int c = n;
			bool aug = false;
			while (!q.empty() && !aug) {
				int x = q.front(); q.pop();
				if (x != bl[x]) continue;
				for (int y = 0; y < c; y++) {
					if (y == bl[y] && adj[x][y] != -1) {
						if (d[y]==0) {
							p[y]=x, d[y]=2, p[mate[y]]=y, d[mate[y]]=1;
							q.push(mate[y]);
						}
						else if (d[y]==1) {
							vector<int> vx = trace(x);
							vector<int> vy = trace(y);
							if (vx.back() == vy.back()) {
								contract(c, vx, vy);
								q.push(c);
								p[c] = p[b[c][0]];
								d[c] = 1;
								c++;
							}
							else {
								aug = true;
								vx.insert(vx.begin(), y);  vy.insert(vy.begin(), x);
								vector<int> A = lift(vx), B = lift(vy);
								A.insert(A.end(), B.rbegin(), B.rend());
								for (int i = 0; i < sz(A); i += 2) {
									match(A[i], A[i+1]);
									if (i+2 < sz(A)) add_edge(A[i+1], A[i+2]);
								}
							}
							break;
						}
					}
				}
			}
			if (!aug) return ans;
		}
	}
};



vector<int> nei[10000];
TwoSAT T1;
Blossom B;
void solve(){
	int n, m; cin >> n >> m; // vertices and edges
	rep(i,0,n)nei[i].clear();
	B.init(n);
	for (int i = 0; i < m; i++) { int a, b; cin >> a >> b;a--,b--;nei[a].push_back(b),nei[b].push_back(a); B.add_edge(a, b); }
	B.solve();
	vector<pair<int,int> >match;
	vector<bool> nmatch(n,true);
	for (int i = 0; i < n; i++)
		if (i < B.mate[i])match.push_back({i,B.mate[i]}),nmatch[i]=false,nmatch[B.mate[i]]=false;
	//trav(a,match)cout<<a.first<<" "<<a.second<<endl;
	T1.init(n);
	rep(i,0,n){
		if(nmatch[i])T1.add_imply(i+1,-i-1);
		trav(a,nei[i]){
			T1.add_or(i+1,a+1);
		}
	}
	trav(a,match)T1.add_xor(a.first+1,a.second+1);
	if(T1.solve()){
		cout<<match.size()<<"\n";
		rep(i,0,n){
			if(T1.answer[i+1])cout<<i+1<<" ";
		}
		cout<<"\n";
		return;
	}
	rep(Fx,0,n){
		T1.init(n);
		if(nmatch[Fx]){
			
			rep(i,0,n){
				if(nmatch[i] && i!=Fx)T1.add_imply(i+1,-i-1);
				trav(a,nei[i]){
					T1.add_or(i+1,a+1);
				}
			}
			trav(a,match)T1.add_xor(a.first+1,a.second+1);
			bool ans=T1.solve();
			//cout<<"A"<<ans<<" "<<Fx<<endl;
			if(ans){
				cout<<match.size()+1<<"\n";
				rep(i,0,n){
					if(T1.answer[i+1])cout<<i+1<<" ";
				}
				cout<<"\n";
				return;
			}
		}else{
			
			rep(i,0,n){
				if(nmatch[i])T1.add_imply(i+1,-i-1);
				trav(a,nei[i]){
					T1.add_or(i+1,a+1);
				}
			}
			trav(a,match){
				if(a.first!=Fx && a.second!=Fx)T1.add_xor(a.first+1,a.second+1);
			}
			bool ans=T1.solve();
			//cout<<"A"<<ans<<" "<<Fx<<endl;
			if(ans){
				cout<<match.size()+1<<"\n";
				rep(i,0,n){
					if(T1.answer[i+1])cout<<i+1<<" ";
				}
				cout<<"\n";
				return;
			}
		}
	}
	cout<<"not smol\n";
}

int main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int tt=1;
	cin>>tt;
	while(tt--){
		//cout<<tt<<"\n";
		solve();
	}
}