#include <cstdlib>
#include <iostream>
#include <vector>
#include <string>
#include <cmath>
#include <unordered_map>
#include <stack>
#include <cassert>
#include <algorithm>
#include <iomanip>
#include <map>
#include <queue>
#include <set>

#include <iostream>
#include <climits>
#include <vector>
#include <cassert>
#include <algorithm>
#include <set>
#include <map>
#include <set>

using namespace std;

vector<vector<int>> gr;
const int MAXN = 1e5 + 100;
int p[MAXN];
bool used[MAXN];
int h[MAXN];
int was[MAXN];
pair<int, int> what[MAXN];

set<pair<int, int>> banned;
vector<pair<int, int>> edges;
void Dfs(int v, int hh = 0) {
    used[v] = true;
    h[v] = hh;
    for (auto el : gr[v]) {
        if (!used[el]) {
            p[el] = v;
            banned.emplace(min(v, el), max(v, el));
            Dfs(v, hh + 1);
        }
    }
}

int main() {
    freopen("input.txt", "r", stdin);
//    freopen("intel.out", "w", stdout);

    ios_base::sync_with_stdio(0);
    cin.tie();

    int T;
    cin >> T;
    while (T--) {
        int n, m;
        cin >> n >> m;
        gr.clear();
        gr.resize(n);
        banned.clear();
        for (int i = 0; i < n; i++) {
            used[i] = false;
            p[i] = -1;
            was[i] = -1;
        }

        for (int i = 0; i < m; i++) {
            int u, v;
            cin >> u >> v;
            u--;
            v--;
            gr[u].push_back(v);
            gr[v].push_back(u);
            edges.emplace_back(min(u, v), max(u, v));
        }
        for (int i = 0; i < n; i++) {
            if (!used[i]) {
                Dfs(i);
            }
        }
        int cnt = 0;

        pair<int, int> e1{-1, -1};
        pair<int, int> e2{-1, -1};
        try {
            for (const auto &edge : edges) {
                if (banned.count(edge)) {
                    continue;
                }
                int u = edge.first;
                int v = edge.second;
                what[cnt] = {u, v};

                if (h[u] > h[v]) {
                    swap(u, v);
                }
                while (h[u] < h[v]) {
                    was[u] = cnt;
                    u = p[u];
                }
                while (u != v) {
                    if (was[u] != -1) {
                        e1 = what[was[u]];
                        e2 = edge;
                        throw 1;
                    }
                    was[u] = cnt;
                    was[v] = cnt;
                    u = p[u];
                    v = p[v];
                }
            }
        } catch (...) {
            set<int> meet;

            auto add = [&](int v) {
                if (meet.count(v)) {
                    meet.erase(v);
                } else {
                    meet.insert(v);
                }
            };

            auto proc = [&](set<pair<int, int>>& st, int u, int v) {
                if (h[u] > h[v]) {
                    swap(u, v);
                }
                while (h[u] < h[v]) {
                    pair<int, int> ee(min(u, p[u]), max(u, p[u]));
                    if (st.count(ee)) {
                        add(ee.first);
                        add(ee.second);
                    }
                    st.insert(ee);
                    u = p[u];
                }
                while (u != v) {
                    pair<int, int> ee1(min(u, p[u]), max(u, p[u]));
                    pair<int, int> ee2(min(v, p[v]), max(v, p[v]));
                    if (st.count(ee1)) {
                        add(ee1.first);
                        add(ee1.second);
                    }
                    if (st.count(ee2)) {
                        add(ee2.first);
                        add(ee2.second);
                    }

                    st.insert(ee1);
                    st.insert(ee2);
                    u = p[u];
                    v = p[v];
                }
            };
            set<pair<int, int>> s1;
            proc(s1, e1.first, e1.second);

            assert(meet.size() == 2);
        }


    }


    return 0;
}