#include <cstdio> 
#include <cstring>
#include <algorithm>
#include <vector>
#include <map>
#include <ctime>
#include <random>
#include <unordered_map>
typedef long long LL;
typedef std::pair<int, int> pii;
#define fi first
#define se second
#define MP std::make_pair
int read()
{
	int f = 1, s = 0;
	char c = getchar();
	while (!(c >= '0' && c <= '9'))
		f ^= c == '-', c = getchar();
	while (c >= '0' && c <= '9')
		s = s * 10 + (c ^ 48), c = getchar();
	return f ? s : -s;
}
template<typename T>
T& Fmin(T& x, T y){ return x = x < y ? x : y; }
template<typename T>
T& Fmax(T& x, T y){ return x = y < x ? x : y; }
const int MAXN = 1005;
int n, m, mat[MAXN], pre[MAXN], col[MAXN];
std::vector<int> e[MAXN];
namespace DSU
{
	int fa[MAXN];
	void init(int n){ std::iota(fa + 1, fa + n + 1, 1); }
	bool isRoot(int x){ return x == fa[x]; }
	int getFath(int x){ return x == fa[x] ? x : (fa[x] = getFath(fa[x])); }
	void merge(int x, int y){ fa[getFath(x)] = getFath(y); }
	bool tog(int x, int y){ return getFath(x) == getFath(y); }
}
int vis[MAXN], tim = 0;
int q[MAXN], fr, ba;
int getLca(int x, int y)
{
	++tim;
	while (vis[x] != tim)
	{
		vis[x] = tim;
		x = DSU::getFath(pre[mat[x]]);
		if (y) std::swap(x, y);
	}
	return x;
}
void shrink(int x, int y, int rt)
{
	while (!DSU::tog(x, rt))
	{
		pre[x] = y, y = mat[x];
		if (DSU::isRoot(x)) DSU::merge(x, rt);
		if (DSU::isRoot(y)) DSU::merge(y, rt);
		if (col[y] == 1) col[y] = 0, q[++ba] = y;
		x = pre[y];
	}
}
bool Blossom(int s)
{
	fr = 1, ba = 0;
	memset(col + 1, -1, n << 2);
	memset(pre + 1, 0, n << 2);
	DSU::init(n);
	col[q[++ba] = s] = 0;
	while (fr <= ba)
	{
		int x = q[fr++];
		for (int y : e[x])
		{
			if (col[y] == 1 || DSU::tog(x, y)) continue;
			if (!col[y])
			{
				int lca = getLca(x, y);
				shrink(x, y, lca), shrink(y, x, lca);
			}
			else
			{
				pre[y] = x, col[y] = 1;
				if (!mat[y])
				{
					for (int i = y, j; i; i = j)
						j = mat[pre[i]], mat[i] = pre[i], mat[pre[i]] = i;
					return true;
				}
				col[q[++ba] = mat[y]] = 0;
			}
		}
	}
	return false;
}
namespace SAT 
{
    int n, N;
    int dfn[MAXN], low[MAXN], st[MAXN], tp, dcnt, bel[MAXN];
    bool inSt[MAXN];
    std::vector<int> e[MAXN];
    void init(int _n)
    {
        dcnt = 0, tp = 0, n = _n, N = 0;
        memset(dfn + 1, 0, n << 3);
        for (int i = 1; i <= n + n; i++) e[i].clear();
    }
    void add(int u, int i, int v, int j){ e[u + i * n].push_back(v + j * n); }
    void tarjan(int x)
    {
        dfn[x] = low[x] = ++dcnt;
        inSt[st[++tp] = x] = true;
        for (int y : e[x])
            if (!dfn[y]) tarjan(y), Fmin(low[x], low[y]);
            else if (inSt[y]) Fmin(low[x], dfn[y]);
        if (low[x] == dfn[x])
        {
            ++N;
            for (int u = 0; u != x; tp--)
                inSt[u = st[tp]] = false, bel[u] = N;
        }
    }
    bool sat(bool cho[])
    {
        for (int i = 1; i <= n + n; i++)
            if (!dfn[i]) tarjan(i);
        for (int i = 1; i <= n; i++)
            if (bel[i] == bel[i + n]) return false;
        for (int i = 1; i <= n; i++)
            cho[i] = bel[i] > bel[i + n];
        return true;
    }
}
int con[MAXN][2], K, id[MAXN];
bool cho[MAXN];
bool chk()
{
    int cur = 0;
    for (int i = 1; i <= n; i++)
        if (mat[i] && i < mat[i])
        {
            con[++cur][0] = i, con[cur][1] = mat[i];
            id[i] = cur << 1, id[mat[i]] = cur << 1 | 1;
        }
    SAT::init(K);
    for (int i = 1; i <= K; i++)
        for (int o = 0; o <= 1; o++)
        {
            int x = con[i][o];
            for (int y : e[x])
                if (!mat[y]) SAT::add(i, o ^ 1, i, o);//, printf("%d %d %d %d\n", i, o, x, y);
                else if (y != mat[x])
                {
                    int j = id[y] >> 1, oo = id[y] & 1;
                    SAT::add(i, o ^ 1, j, oo);
                    SAT::add(j, oo ^ 1, i, o);
                }
        }
    return SAT::sat(cho);
}
bool chk1(int key)
{
    SAT::init(K + 1), SAT::add(K + 1, 1, K + 1, 0);
    for (int i = 1; i <= K; i++)
        for (int o = 0; o <= 1; o++)
        {
            int x = con[i][o];
            for (int y : e[x])
                if (!mat[y] && y != key) SAT::add(i, o ^ 1, i, o);
                else if (y != mat[x] && y != key)
                {
                    int j = id[y] >> 1, oo = id[y] & 1;
                    SAT::add(i, o ^ 1, j, oo);
                    SAT::add(j, oo ^ 1, i, o);
                }
        }
    return SAT::sat(cho);
}
int main()
{
    for (int T = read(); T--; )
    {
        n = read(), m = read();
        for (int i = 1, u, v; i <= m; i++)
        {
            u = read(), v = read();
            e[u].push_back(v), e[v].push_back(u);
        }
        K = 0;
        for (int i = 1; i <= n; i++)
            if (!mat[i]) K += Blossom(i);
        if (chk())
        {
            printf("%d\n", K);
            for (int i = 1; i <= K; i++)
                printf("%d%c", con[i][cho[i]], " \n"[i == K]);
        }
        else
        {
            bool vld = false;
            for (int i = 1; i <= n; i++)
                if (!mat[i] && chk1(i))
                {
                    printf("%d\n", K + 1);
                    for (int j = 1; j <= K; j++)
                        printf("%d ", con[j][cho[j]]);
                    printf("%d\n", i);
                    vld = true; break;
                }
            if (!vld) printf("not smol\n");
        }
        for (int i = 1; i <= n; i++) e[i].clear();
        memset(mat + 1, 0, n << 2);
    }
	return 0;
}