#include <bits/stdc++.h>

using i64 = long long;
using u64 = unsigned long long;
using u32 = unsigned;

void solve() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<std::vector<int>> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    std::vector<bool> del(n);
    std::vector<int> col(n, -1);
    std::queue<int> q;
    col[0] = 0;
    q.push(0);
    
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        for (auto y : adj[x]) {
            if (col[x] == col[y]) {
                std::cout << "NO\n";
                return;
            }
            if (col[y] == -1) {
                col[y] = col[x] ^ 1;
                q.push(y);
            }
        }
    }
    
    std::vector<bool> f(n);
    
    for (int c = 0; c < 2; c++) {
        for (int x = 0; x < n; x++) {
            if (del[x] || col[x] != c) {
                continue;
            }
            for (auto y : adj[x]) {
                if (!del[y] && adj[y].size() == 2) {
                    int z = adj[y][0] ^ adj[y][1] ^ x;
                    if (f[z]) {
                        del[y] = true;
                        adj[y].clear();
                    } else {
                        f[z] = true;
                    }
                }
            }
            for (auto y : adj[x]) {
                if (!del[y] && adj[y].size() == 2) {
                    int z = adj[y][0] ^ adj[y][1] ^ x;
                    f[z] = false;
                }
            }
        }
        for (int x = 0; x < n; x++) {
            if (del[x] || col[x] != c) {
                continue;
            }
            adj[x].erase(std::remove_if(adj[x].begin(), adj[x].end(),
                [&](int y) {
                    return del[y];
                }), adj[x].end());
        }
    }
    
    int rt = 0;
    while (del[rt]) {
        rt++;
    }
    
    std::vector<std::vector<int>> cyc;
    
    std::vector<bool> vis(n);
    std::vector<int> p(n, -1), dep(n);
    auto dfs = [&](auto &&self, int x) -> void {
        vis[x] = true;
        for (auto y : adj[x]) {
            if (!vis[y]) {
                dep[y] = dep[x] + 1;
                p[y] = x;
                self(self, y);
            } else if (dep[y] > dep[x]) {
                if (cyc.size() <= 2) {
                    std::vector<int> a;
                    for (int i = y; i != p[x]; i = p[i]) {
                        a.push_back(i);
                    }
                    cyc.push_back(a);
                }
            }
        }
    };
    dfs(dfs, rt);
    
    if (cyc.empty()) {
        std::cout << "YES\n";
        return;
    }
    for (auto &a : cyc) {
        if (a.size() != 4) {
            std::cout << "NO\n";
            return;
        }
    }
    std::vector<int> h(n);
    for (int x = 0; x < n; x++) {
        if (del[x]) {
            continue;
        }
        if (adj[x].size() > 2) {
            h[x] = 1;
        }
        int cnt = 0;
        for (auto y : adj[x]) {
            if (adj[y].size() >= 2) {
                cnt++;
            }
        }
        if (cnt > 2) {
            h[x] = 2;
        }
    }
    for (auto c : cyc) {
        int c1 = 0;
        int c2 = 0;
        for (auto x : c) {
            if (h[x] == 2) {
                c2++;
            }
            if (h[x]) {
                c1++;
            }
        }
        if (c1 == 4 || c2 > 1) {
            std::cout << "NO\n";
            return;
        }
    }
    std::cout << "YES\n";
}

void brute() {
    int n, m;
    std::cin >> n >> m;
    
    std::vector<int> adj(n);
    for (int i = 0; i < m; i++) {
        int u, v;
        std::cin >> u >> v;
        u--;
        v--;
        adj[u] |= 1 << v;
        adj[v] |= 1 << u;
    }
    
    std::vector<int> f(1 << n);
    std::vector<bool> vis(1 << n);
    std::queue<int> q;
    
    for (int s = 1; s < (1 << n); s++) {
        int i = __builtin_ctz(s);
        f[s] = f[s ^ (1 << i)] | adj[i];
    }
    
    std::vector<std::vector<std::array<int, 2>>> e(1 << n);
    for (int s = 0; s < (1 << n); s++) {
        if (__builtin_popcount(s) <= 2) {
            vis[s] = true;
            q.push(s);
        } else {
            for (int t = (s - 1) & s; t; t = (t - 1) & s) {
                int u = t;
                int v = t ^ s;
                if (__builtin_popcount(u) >= 2) {
                    u = f[u];
                }
                if (__builtin_popcount(v) >= 2) {
                    v = f[v];
                }
                e[u].push_back({v, s});
                e[v].push_back({u, s});
            }
        }
    }
    
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        
        for (auto [y, z] : e[x]) {
            if (vis[y] && !vis[z]) {
                vis[z] = true;
                q.push(z);
            }
        }
    }
    
    if (vis[(1 << n) - 1]) {
        std::cout << "YES\n";
    } else {
        std::cout << "NO\n";
    }
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int T;
    std::cin >> T;
    
    while (T--) {
        solve();
    }
    
    return 0;
}