我觉得我写得已经和题解一模一样了，不知道为什么就是过不了。。懒得拍了，反正不是很难，不太想浪费时间。
1~2~3的一条路径相当于从2~1的一条路径+2~3的一条路径，点不能重复经过，于是拆点。
//Achen
#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdlib>
#include<vector>
#include<cstdio>
#include<queue>
#include<cmath>
#include<set>
#include<map>
#define Formylove return 0
#define For(i,a,b) for(int i=(a);i<=(b);i++)
#define Rep(i,a,b) for(int i=(a);i>=(b);i--)
const int N=;
typedef long long LL;
typedef double db;
using namespace std;
int n,m; template<typename T>void read(T &x) {
char ch=getchar(); x=; T f=;
while(ch!='-'&&(ch<''||ch>'')) ch=getchar();
if(ch=='-') f=-,ch=getchar();
for(;ch>=''&&ch<='';ch=getchar()) x=x*+ch-''; x*=f;
} struct edge {
int u,v,cap,fl,nx;
edge(){}
edge(int u,int v,int cap,int fl,int nx):u(u),v(v),cap(cap),fl(fl),nx(nx){}
}e[N]; int ecnt=,fir[N];
void add(int u,int v,int cap) {
e[++ecnt]=edge(u,v,cap,,fir[u]); fir[u]=ecnt;
//printf("%d->%d:%d\n",u,v,cap);
e[++ecnt]=edge(v,u,,,fir[v]); fir[v]=ecnt;
} queue<int>que;
int d[N];
void bfs(int s,int t) {
que.push(t);
For(i,,n) d[i]=n;
d[t]=;
while(!que.empty()) {
int x=que.front();
que.pop();
for(int i=fir[x];i;i=e[i].nx) {
int y=e[i].v;
if(d[y]==n&&e[i].cap==) {
d[y]=d[x]+;
que.push(y);
}
}
}
} #define inf 1e9
int p[N];
int calc(int s,int t) {
int fl=inf;
for(int i=t;i!=s;i=e[p[i]].u)
fl=min(fl,e[p[i]].cap-e[p[i]].fl);
for(int i=t;i!=s;i=e[p[i]].u)
e[p[i]].fl+=fl,e[p[i]^].fl-=fl;
return fl;
} int c[N],cur[N];
int isap(int s,int t) {
For(i,,n) c[i]=;
bfs(s,t);
For(i,,n) cur[i]=fir[i],c[d[i]]++;
int rs=;
for(int x=s;d[x]<n;) {
if(x==t) {
rs+=calc(s,t);
x=s;
}
int ok=;
for(int &i=cur[x];i;i=e[i].nx) if(e[i].cap>e[i].fl&&d[e[i].v]+==d[x]) {
ok=; p[x=e[i].v]=i; break;
}
if(!ok) {
int D=n; cur[x]=fir[x];
for(int i=fir[x];i;i=e[i].nx) if(e[i].cap>e[i].fl)
D=min(D,d[e[i].v]+);
if(!(--c[d[x]])) break;
c[d[x]=D]++;
if(x!=s) x=e[p[x]].u;
}
}
return rs;
} void init() {
ecnt=;
memset(fir,,sizeof(fir));
} int main() {
#ifdef ANS
freopen(".in","r",stdin);
freopen(".out","w",stdout);
#endif
int T; read(T);
while(T--) {
init();
read(n); read(m);
int s=*n+,t=s+;
For(i,,n) add(i,i+n,);
add(s,n+,);
add(,t,);
add(,t,);
For(i,,m) {
int x,y;
read(x); read(y);
if(x<||x>n||y<||y>n) continue;
add(x+n,y,);
add(y+n,x,);
}
n=t;
if(isap(s,t)==) puts("YES");
else puts("NO");
}
Formylove;
}