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

int main() {
    ll T; cin >> T;
    for(ll t = 0; t < T; t++) {
        ll N, M; cin >> N >> M;

        vector<vector<ll>> adj(N);
        for(ll i = 0; i < M; i++) {
            ll U,V; cin >> U >> V; U--;V--;
            adj[U].push_back(V); adj[V].push_back(U);
        }

        if(N <= 3) {
            cout << "YES\n"; continue;
        }

        // complete graph: always fail.
        if(M == (N*(N-1))/2 || M == 0) {
            cout << "YES\n"; continue;
        }

        map<ll,ll> counts;
        for(ll i = 0; i < N; i++) counts[adj[i].size()]++;

        bool star = (counts[1]== N-1 && counts[N-1] = 1);
        bool clique = (counts[N-2]== N-1 && counts[0] == 1);
        if(star || clique) {
            cout << "YES\n"; continue;
        }

        // if there is a vertex with degree in the range [2..N-2], now always possible; (N-1 choose 2) > N

        if(N > 5) {
            // in big graphs even if all vertices are small, there are enough matchings.
            cout << "NO\n"; continue;
        }

        vector<vector<pair<ll,ll>>> results;

        vector<ll> permu;
        for(ll i = 0; i < N; i++) permu.push_back(i);

        do {
            vector<pair<ll,ll>> ed;
            for(ll i = 0; i < N; i++) {
            for(auto a: adj[i]) {
                ed.push_back({permu[i], permu[a]});
            }
            }

            sort(ed.begin(), ed.end());

            bool contained = false; for(auto r: results) if(r == ed) contained = true;

            if(!contained) results.push_back(ed);
        } while(next_permutation(permu.begin(), permu.end()));

        if(results.size() > N) cout << "NO\n";
        else cout << "YES\n";
        


        
    }
}

answer.code: In function ‘int main()’:
answer.code:28:38: error: lvalue required as left operand of assignment
   28 |         bool star = (counts[1]== N-1 && counts[N-1] = 1);