#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 = vector<vector<int>>(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;

    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();
}