#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
const int mod = 998244353;
// vector<pii> generalMatching(int N, vector<pii>& ed) {
// vector<vector<ll>> mat(N, vector<ll>(N)), A;
// for (pii pa : ed) {
// int a = pa.first, b = pa.second, r = rand() % mod;
// mat[a][b] = r, mat[b][a] = (mod - r) % mod;
// }
// int r = matInv(A = mat), M = 2 * N - r, fi, fj;
// assert(r % 2 == 0);
// if (M != N) do {
// mat.resize(M, vector<ll>(M));
// rep(i,0,N) {
// mat[i].resize(M);
// rep(j,N,M) {
// int r = rand() % mod;
// mat[i][j] = r, mat[j][i] = (mod - r) % mod;
// }
// }
// }
// }
#define rep(i, l, r) for (int i = l; i < (r); i++)
#define sz(a) (int) (a).size()
#define all(a) begin(a), end(a)
#define vi vector<int>
struct blossom {
int n, m;
vector<int> mate;
vector<vector<int>> b;
vector<int> p, d, bl;
vector<vector<int>> g;
blossom(int n) : n(n) {
m = n + n / 2;
mate.assign(n, -1);
b.resize(m);
p.resize(m);
d.resize(m);
bl.resize(m);
g.assign(m, vector<int>(m, -1));
}
void add_edge(int u, int v) {
g[u][v] = u;
g[v][u] = v;
}
void match(int u, int v) {
g[u][v] = g[v][u] = -1;
mate[u] = v;
mate[v] = u;
}
vector<int> trace(int x) {
vector<int> vx;
while (true) {
while (bl[x] != x) x = bl[x];
if (!vx.empty() && vx.back() == x) break;
vx.push_back(x);
x = p[x];
}
return vx;
}
void contract(int c, int x, int y, 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++) {
g[c][i] = g[i][c] = -1;
}
for (int z : b[c]) {
bl[z] = c;
for (int i = 0; i < c; i++) {
if (g[z][i] != -1) {
g[c][i] = z;
g[i][c] = g[i][z];
}
}
}
}
vector<int> lift(vector<int>& vx) {
vector<int> A;
while (vx.size() >= 2) {
int z = vx.back(); vx.pop_back();
if (z < n) {
A.push_back(z);
continue;
}
int w = vx.back();
int i = (A.size() % 2 == 0 ? find(b[z].begin(), b[z].end(), g[z][w]) - b[z].begin() : 0);
int j = (A.size() % 2 == 1 ? find(b[z].begin(), b[z].end(), g[z][A.back()]) - b[z].begin() : 0);
int k = b[z].size();
int dif = (A.size() % 2 == 0 ? i % 2 == 1 : j % 2 == 0) ? 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(d.begin(), d.end(), 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 (bl[x] != x) continue;
for (int y = 0; y < c; y++) {
if (bl[y] == y && g[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, x, y, 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);
vector<int> B = lift(vy);
A.insert(A.end(), B.rbegin(), B.rend());
for (int i = 0; i < (int)A.size(); i += 2) {
match(A[i], A[i + 1]);
if (i + 2 < (int)A.size()) add_edge(A[i + 1], A[i + 2]);
}
}
break;
}
}
}
}
if (!aug) return ans;
}
}
};
struct TwoSat {
int N;
vector<vector<int>> gr;
vector<int> values;
TwoSat(int n = 0) : N(n), gr(2 * n) {}
int addVar() {
gr.emplace_back();
gr.emplace_back();
return N++;
}
void either(int f, int j) {
f = max(2 * f, -1 - 2 * f);
j = max(2 * j, -1 - 2 * j);
gr[f].push_back(j ^ 1);
gr[j].push_back(f ^ 1);
}
void setValue(int x) { either(x, x); }
void atMostOne(const vector<int>& li) {
if (li.size() <= 1) return;
int cur = ~li[0];
rep(i,2,sz(li)) {
int next = addVar();
either(cur, ~li[i]);
either(cur, next);
either(~li[i], next);
cur = ~next;
}
either(cur, ~li[1]);
}
vector<int> val, comp, z;
int time = 0;
int dfs(int i) {
int low = val[i] = ++time, x;
z.push_back(i);
for (int e : gr[i])
if(!comp[e]) low = min(low, val[e] ?: dfs(e));
if (low == val[i]) do {
x = z.back();
z.pop_back();
comp[x] = low;
if (values[x >> 1] == -1) values[x >> 1] = x & 1;
} while(x != i);
return val[i] = low;
}
bool solve() {
values.assign(N, -1);
val.assign(2 * N, 0);
comp = val;
rep(i,0,2*N) if(!comp[i]) dfs(i);
rep(i,0,N) if(comp[2*i] == comp[2*i+1]) return 0;
return 1;
}
};
void solve() {
int n,m; cin >> n >> m;
vector<pii> edges;
blossom blossom(n);
for (int i = 0; i < m; i++) {
int u,v; cin >> u >> v; u--; v--;
edges.emplace_back(u, v);
blossom.add_edge(u, v);
}
blossom.solve();
return 0;
vector<int> unmatched;
vector<pii> matching;
for (int u = 0; u < n; u++) {
if (blossom.mate[u] == -1)
unmatched.emplace_back(u);
else if (blossom.mate[u] > u)
matching.emplace_back(u, blossom.mate[u]);
}
// cout << "Matching:\n";
// for (auto& [u, v] : matching)
// cout << '(' << u << ' ' << v << ") ";
// cout << '\n';
auto test = [&](const vector<int>& forced_vertices) -> pair<bool, TwoSat> {
vector<bool> forced(n, false);
for (auto& u : forced_vertices) forced[u] = true;
TwoSat twosat(n);
for (auto& u : forced_vertices) twosat.setValue(u);
for (auto& u : unmatched) if (!forced[u]) twosat.setValue(~u);
for (auto& [u, v] : edges) twosat.either(u, v);
for (auto& [u, v] : matching) if (!forced[u] && !forced[v]) twosat.either(~u, ~v);
bool res = twosat.solve();
// cout << "TwoSat " << res << "\n";
// for (int u = 0; u < n; u++)
// cout << twosat.values[u] << " \n"[u + 1 == n];
return make_pair(res, twosat);
};
const int M = (int)matching.size();
int mvc_size = -1;
TwoSat sol;
// test if answer = M
{
auto [res, twosat] = test({});
if (res) {
mvc_size = M;
sol = twosat;
goto done;
}
}
// test if answer = M + 1
for (auto& [u, v] : matching) {
auto [res, twosat] = test({u, v});
if (res) {
mvc_size = M + 1;
sol = twosat;
goto done;
}
}
for (auto& u : unmatched) {
auto [res, twosat] = test({u});
if (res) {
mvc_size = M + 1;
sol = twosat;
goto done;
}
}
done:;
if (mvc_size == -1) {
cout << "not smol\n";
}
else {
vector<int> ans;
for (int u = 0; u < n; u++)
if (sol.values[u])
ans.emplace_back(u);
cout << mvc_size << '\n';
for (int i = 0; i < mvc_size; i++)
cout << ans[i] + 1 << " \n"[i + 1 == mvc_size];
}
}
signed main() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(nullptr);
#endif
int T = 1;
cin >> T;
while (T--) solve();
}