#pragma comment(linker, "/STACK:102400000,102400000")
#include<stdio.h>
#include<cstring>
#include<algorithm>
using namespace std;
int next[600005],last[100005],to[600005];
int i,j,k,l,s,m,n,tot,test,x,y,ans1,ans2,vis[100005],a[100005],dis[100005],f[100005],b[100005],dfn,ia[100005];
inline void add(int o,int p) {
    next[++tot]=last[o]; last[o]=tot; to[tot]=p;
}
inline void dfs(int x,int o,int q,int fa,int p){
    if (ans1&&ans2) return;
    vis[x]=1; a[x]=q; f[x]=fa; dis[x]=p; ia[x]=++dfn;
    for (int i=last[x];i;i=next[i])
    if (i!=(o^1)) {
    if (!vis[to[i]]) dfs(to[i],i,q^1,x,p+1);
        else {
        if (a[x]!=a[to[i]]) ans2=1;
        else {
        ans1=1;
        if (!ans2&&ia[x]<ia[to[i]]) {
            int gt=x,gtw=to[i];
            if (dis[gt]<dis[gtw]) swap(gt,gtw);
            while (dis[gt]>dis[gtw]) {
                    if (b[gt]) ans2=1; b[gt]=1; gt=f[gt];
                }
                while (gt!=gtw) {
                    if (b[gt]||b[gtw]) ans2=1;
                    b[gt]=b[gtw]=1; gt=f[gt];gtw=f[gtw];
                }
                if (b[gt]) ans2=1;
                b[gt]=1;
            }
        }
        }
    }
}
int main(){
    scanf("%d",&test);
    while (test--) {
        scanf("%d%d",&n,&m); tot=1; ans1=ans2=dfn=0;
        memset(vis,0,sizeof(vis));
        memset(b,0,sizeof(b));
        for (i=1;i<=m;i++) {
            scanf("%d%d",&x,&y);
            add(x,y); add(y,x);
        }
        for (i=1;i<=n;i++)
        if (!vis[i]) dfs(i,0,0,0,0);
        if (ans1) printf("YES\n");
        else printf("NO\n");
        if (ans2) printf("YES\n");
        else printf("NO\n");
        for (i=1;i<=n;i++) last[i]=0;
    }
}