#include<random>
#include<iostream>
#include<iomanip>
#include<ctime>
#include<cmath>
#include<cctype>
#include<cstdio>
#include<cstdlib>
#include<climits>
// #define NDEBUG
#include<cassert>
#include<cstring>
#include<complex>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<queue>
#include<bitset>
#include<vector>
// #define LL __int128
#define LL long long
#define ULL unsigned LL
#define uint unsigned int
// #define int LL
// #define double long double
#define mkp make_pair
#define par pair<int,int>
#define epb emplace_back
#define psb push_back
#define f(x) ((x).first)
#define s(x) ((x).second)
using namespace std;
#define Lbt(x) ((x)&(-(x)))
#define Swap(x,y) (x^=y^=x^=y)
const int Mxxx=1e5;
inline char gc()
{
    // return getchar();
    static char buf[Mxxx],*p1=buf,*p2=buf;
    return (p1==p2&&(p2=(p1=buf)+fread(buf,1,Mxxx,stdin),p1==p2))?EOF:*p1++;
}
inline char pc(char ch,bool fl=false)
{
    // return fl?0:putchar(ch),0;
    static char buf[Mxxx],*p1=buf,*p2=buf+Mxxx;
    return (fl||((*p1++=ch)&&p1==p2))&&(fwrite(buf,1,p1-buf,stdout),p1=buf),0;
}
#define output pc('!',true)
inline int read()
{
    char ch=gc();
    int gans=0,gflag=0;
    for(;ch<'0'||'9'<ch;ch=gc())gflag|=(ch=='-');
    for(;'0'<=ch&&ch<='9';ch=gc())gans=(gans<<1)+(gans<<3)+(ch^48);
    return gflag?-gans:gans;
}
template<typename T>
inline char read(T&gans)
{
    char ch=gc();
    int gflag=0;gans=0;
    for(;ch<'0'||'9'<ch;ch=gc())gflag|=(ch=='-');
    for(;'0'<=ch&&ch<='9';ch=gc())gans=(gans<<1)+(gans<<3)+(ch^48);
    return gans=gflag?-gans:gans,ch;
}
template<typename T>
inline void write(T x)
{
    if(x>9)write(x/10);
    pc(x%10^48);
}
template<typename T>
inline void writenum(T x,char ch)
{
    if(x<0)x=-x,pc('-');
    write(x),pc(ch);
}
inline void writechar(char x,char ch)
{
    pc(x),pc(ch);
}
template<typename T>
inline T Max(T x,T y)
{
    return x>y?x:y;
}
template<typename T>
inline T Min(T x,T y)
{
    return x<y?x:y;
}
template<typename T>
inline T Abs(T x)
{
    return x<0?-x:x;
}
template<typename T>
inline void ckmx(T&x,T y)
{
    x=Max(x,y);
}
template<typename T>
inline void ckmn(T&x,T y)
{
    x=Min(x,y);
}
int TT,n,m,psx[100000],psy[100000],G[1000][1000];
int vs[100000];
inline int DFS(int x,int y)
{
    if(x==y)return 1;
    if(vs[x])return 0;
    vs[x]=1;
    int i;
    for(i=1;i<=n;i++)if(G[x][i]&&DFS(i,y))return 1;
    return 0;
}
inline int Chk(int x,int y)
{
    int i;
    for(i=1;i<=n;i++)vs[i]=0;
    return DFS(x,y);
}
int rtx,rty;
inline int Fnd_Cor(int x,int y)
{
    int i,k,s=1,mx=0;
    for(i=1;i<=n;i++)if(i^y&&G[x][i])
    {
        k=Fnd_Cor(i,x);
        s+=k;ckmx(mx,k);
    }
    if((Max(mx,n-s)<<1)<=n)
    {
        if(rtx)assert(!rty),rty=x;else rtx=x;
    }
    return s;
}
const int M=1e6;
int tot,pri[M+5],vst[M+5];
int ck,flg;
#undef par
#define par pair<ULL,ULL>
par ans;
inline ULL Get(int x,int y,int&t)
{
    int i,k,sz=1;ULL s=1;
    for(i=1;i<=n;i++)if(i^y&&G[x][i])s+=Get(i,x,k)*pri[k+233],sz+=k;
    return t=sz,s;
}
inline void Ck()
{
    int i,j,t=0;
    for(i=1;i<=n;i++)for(j=i+1;j<=n;j++)t+=G[i][j];
    assert(t<n);
    if(t<n-1)return;
    rtx=rty=0;
    assert(Fnd_Cor(1,0)==n);
    int sz;
    par pr=mkp(Get(rtx,0,sz),Get(rty,0,sz));
    if(f(pr)<s(pr))Swap(f(pr),s(pr));
    // cout<<"Ck:"<<f(pr)<<" "<<s(pr)<<"\n";
    if(!flg)flg=1,ans=pr;else ck|=(ans!=pr);
}
inline void DFS(int x)
{
    if(x==m+1)
    {
        Ck();
        return;
    }
    int a,b;
    if(!Chk(a=psx[x],b=psy[x]))
    {
        G[a][b]=G[b][a]=1;
        DFS(x+1);
        G[a][b]=G[b][a]=0;
    }
    DFS(x+1);
}
signed main()
{
    #ifndef ONLINE_JUDGE
    freopen("_.in","r",stdin);
    // freopen("_.out","w",stdout);
    #endif
    int i,j;
    for(i=2;i<=M;i++)
    {
        if(!vst[i])
        {
            vst[i]=i;
            pri[++tot]=i;
        }
        for(j=1;j<=tot;j++)
        {
            if(pri[j]*i>M)break;
            vst[pri[j]*i]=pri[j];
            if(vst[i]==pri[j])break;
        }
    }
    for(TT=read();TT;TT--)
    {
        flg=0;ck=0;
        n=read();m=read();
        // for(i=1;i<=n;i++)for(j=1;j<=n;j++)G[i][j]=0;
        for(i=1;i<=m;i++)psx[i]=read(),psy[i]=read();
        DFS(1);
        puts(ck?"NO":"YES");
    }
    return output;
}
/*

*/