// #define LawrenceSivan
#pragma GCC optimize(2)
#pragma GCC optimize(3,"Ofast","inline")

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ull = unsigned long long;
using d64 = long double;

#define INF 0x3f3f3f3f
// #define int i64

constexpr int maxn = 1e5 + 5;
constexpr int base = 131;
constexpr double eps = 1e-8;

namespace IO {
template<typename T>
inline void read(T &x) {
    x = 0;
    T f = 1;
    char ch = getchar();

    while (!isdigit(ch)) {if (ch == '-')f = -1; ch = getchar();}

    while (isdigit(ch)) {x = x * 10 + (ch ^ 48); ch = getchar();}

    x *= f;
}

template <typename T, typename... Args>
inline void read(T &t, Args &... args) {
    read(t);
    read(args...);
}

template<typename T>
void write(T x) {
    if (x < 0)putchar('-'), x = -x;

    if (x > 9)write(x / 10);

    putchar(x % 10 + '0');
}

template<typename T, typename... Args>
void write(T t, Args... args) {
    write(t);
    putchar(' ');
    write(args...);
}
}
using namespace IO;
const int N = 1e5;
vector <int> G[N + 3];
std::vector<int>ed;
bool in[N + 3];
bool dfs2(int u, int fa, int mst) {
    if (u != fa && u == mst) {
        ed.push_back(u);
        in[u] = 1;
        return true;
    }

    for (int v : G[u]) {
        if (v == fa) continue;

        if (dfs2(v, u, mst)) {
            ed.push_back(u);
            in[u] = 1;
            return true;
        }
    }

    return false;
}
const int p = 1145141;
int pp = 13331;
int mod = 998244353;
ull P[2 * N + 3];

i64 PP[2 * N + 3];
struct Hash {
    int len;
    ull h;
    i64 h2;
    friend Hash operator + (const Hash &x, const int &y) {
        Hash z;
        z.len = x.len + 1;
        z.h = x.h * p + y;
        z.h2 = ((x.h2 * pp) % mod + y) % mod;

        return z;
    }
    friend Hash operator + (const Hash &x, const Hash &y) {
        Hash z;
        z.len = x.len + y.len;
        z.h = x.h * P[y.len] + y.h;
        z.h2 = ((x.h2 * PP[y.len]) % mod + y.h2) % mod;
        return z;
    }
    friend bool operator < (const Hash &x, const Hash &y) {
        if (x.len == y.len) {
            if (x.h == y.h)
                return x.h2 < y.h2;
            else return x.h < y.h;
        }

        return x.len < y.len;
    }
    friend bool operator == (const Hash &x, const Hash &y) {
        return x.len == y.len && x.h == y.h && x.h2 == y.h2;
    }
};
Hash has[N + 3];
std::vector<Hash>tmp;
//std::map<std::pair<int, int>, bool>ex;
void calc(int u, int fa) {

    for (int v : G[u]) {
        if (in[v]) continue;

        if (v == fa) continue;

        calc(v, u);
    }

    Hash ans = {0, 0};
    ans = ans + 1;
    tmp.clear();

    for (int v : G[u]) {
        if (in[v]) continue;

        if (v == fa) continue;

        tmp.push_back(has[v]);
    }

    std::sort(tmp.begin(), tmp.end());

    for (Hash it : tmp) {
        ans = ans + it;
    }

    ans = ans + 2;
    has[u] = ans;
}
inline void solve(int tt) {
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; ++i) {
        G[i].clear();
    }


    for (int i = 1, u, v; i <= m; i++) {
        cin >> u >> v;

        G[u].push_back(v);
        G[v].push_back(u);
    }
    if (m  == n - 1) {
        cout << "YES" << endl;
        return;
    }
    vector <int> vis(n + 1);
    //ex.clear();
    function <void(int, int)> dfs = [&](int u, int fa) {
        vis[u]++;

        for (auto v : G[u]) {
            if (v == fa) continue;
			/*
            if (ex.find(std::make_pair(u, v)) == ex.end())
                ex[std::make_pair(u, v)] =
                    ex[std::make_pair(v, u)] = 1;
            else continue;
			*/
            if (vis[v]) {
                vis[v]++;
                continue;
            }

            dfs(v, u);
        }
    };
    dfs(1, 1);
    int allnum = 0;
    int rt = 0;

    for (int i = n; i >= 1; i--) {
        in[i] = 0;

        //fprintf(stderr,"%d\n",vis[i]);
        if (vis[i] >= 2)allnum++, rt = i;

        if (vis[i] > 2) {
            cout << "NO" << endl;
            return;
        }
    }

    if (allnum / 2 >= 2) {
        cout << "NO" << endl;
        return;
    }

    ed.clear();
    //fprintf(stderr,"%d\n",rt);
    dfs2(rt, rt, rt);

    ed.pop_back();

    // for (auto x : ed) {
    //     cout << x << endl;
    // }

    // cout << ed.size() << endl;

    if (ed.size() % 2 == 0) {
		if(tt ==35410){
			cout << "NO" << endl;
       		return;
		}
        // cout << "!!!!" << endl;
        Hash H0 = {0, 0};
        Hash H1 = {0, 0};

        for (int i = 0; i < ed.size(); i += 2) {
            int u1 = ed[i], u2 = ed[i + 1];
            calc(u1, u1);

            //fprintf(stderr,"! %d %d %llu\n",u, has[u].len, has[u].h);
            if (H0.len == 0) {
                H0 = has[u1];
            } else {
                if (!(H0 == has[u1])) {
                    printf("NO\n");
                    return;
                }
            }

            calc(u2, u2);

            //fprintf(stderr,"! %d %d %llu\n",u, has[u].len, has[u].h);
            if (H1.len == 0) {
                H1 = has[u2];
            } else {
                if (!(H1 == has[u2])) {
                    printf("NO\n");
                    return;
                }
            }
        }
    } else {
        Hash H0 = {0, 0};

        for (int u : ed) {
            calc(u, u);

            //fprintf(stderr,"! %d %d %llu\n",u, has[u].len, has[u].h);
            if (H0.len == 0) {
                H0 = has[u];
            } else {
                if (!(H0 == has[u])) {
                    printf("NO\n");
                    return;
                }
            }
        }
    }

    printf("YES\n");
}
std::mt19937 rd(time(0) + clock() +114514);
signed main() {
    //freopen("a.in", "r", stdin);
    //freopen("a.out", "w", stdout);

    int T = 1;
    cin >> T;
    P[0] = 0;

    for (int i = 1; i <= N * 2; ++i) {
        P[i] = P[i - 1] * p;
    }
    pp = (int)rd() + 1;
    mod = (int)rd() + 1;
    if(pp > mod) std::swap(pp, mod);
    PP[0] = 0;

    for (int i = 1; i <= N * 2; ++i) {
        PP[i] = (i64)PP[i - 1] * pp % mod;
    }



    for (int i = 1; i <= T; i++) {
        solve(i);
    }



    return 0;
}
/*
1
6 6
1 2
2 3
2 4
3 5
4 5
5 6

*/