代码：

#include<bits/stdc++.h>
#define int long long
#define N 100005
#define M 4001005
using namespace std;
int T,n,m,x[M],y[M],st[N];
int h[N],e[M],ne[M],idx;
bool edge[2009][2009];
void add(int a,int b){
	e[idx]=b;ne[idx]=h[a];h[a]=idx++;
}
bool dfs(int u,int c){
	st[u]=c;
	for(int i=h[u];~i;i=ne[i]){
		int j=e[i];
		if(!st[j]){
			if(!dfs(j,3-c))return 0;
		}
		else if(st[j]==c)return 0;
	}
	return 1;
}
void solve(int cs){
	cin>>n>>m;
	if(n<=2002){
		for(int i=1;i<=n;i++){
			st[i]=0;
			for(int j=i+1;j<=n;j++){
				edge[i][j]=0;
			}
		}
	}
	for(int i=1;i<=m;i++){
		cin>>x[i]>>y[i];
		if(n<=2002)edge[x[i]][y[i]]=edge[y[i]][x[i]]=1;
	}
	if(n>2002){
		cout<<"No\n";
		return;
	}
	idx=0;
	for(int i=1;i<=n;i++){
		h[i]=-1;
		for(int j=i+1;j<=n;j++){
			if(!edge[i][j])add(i,j),add(j,i);
		}
	}
	bool flag=1;
	for(int i=1;i<=n;i++){
		if(!st[i]){
			if(!dfs(i,1)){
				flag=0;
				break;
			}
		}
	}
	cout<<(flag?"Yes\n":"No\n");
}
signed main(){
	cin>>T;
	for(int cs=1;cs<=T;cs++){
		solve(cs);
	}
	return 0;
}