#include<bits/stdc++.h>
using namespace std;
vector<int>g[300005];
int vist[300005];
int tt;
int a1[300005],a2[300005];
vector<int>vc;
int v[300005],tms=0;
void getall(int x){
	++tms;
	queue<int>q;
	q.emplace(x);
	v[x]=tms;
	while(q.size()){
		int x=q.front();
		vist[x]=1;
		q.pop();
		vc.emplace_back(x);
		for(auto cu:g[x]){
			if(v[cu]==tms)continue;
			v[cu]=tms;
			q.emplace(cu);
		}
	}
}
int cc[300005];
bool ranse(int x){
	if(a2[x])return 1;
	a2[x]=++tt;
	vector<int>lj;
	for(auto cu:g[x]){
		if(a1[cu]==a1[x]||a2[cu])continue;
		lj.emplace_back(cu);
	}
	for(auto cu:lj)++cc[cu];
	int gs=0;
	for(auto cu:lj){
		for(auto uc:g[cu]){
			if(cc[uc])++gs;
		}
	}
	for(auto cu:lj)--cc[cu];
	int sz=lj.size();
	if(gs!=1ll*sz*(sz-1))return 0;
	for(auto cu:lj){
		if(a1[cu])a2[cu]=tt;
		else a1[cu]=tt;
	}
	for(auto cu:lj){
		if(!a2[cu]){
			if(!ranse(cu))return 0;
		}
	}
	return 1;
}
bool test(int x,auto vc,auto s1,auto s2){
	for(auto cu:s1)cc[cu]=1;
	for(auto cu:s2)cc[cu]=2;
	int zh=0;
	for(auto cu:s1){
		for(auto uc:g[cu]){
			if(cc[uc]==1)++zh;
		}
	}
	for(auto cu:s2){
		for(auto uc:g[cu]){
			if(cc[uc]==2)++zh;
		}
	}
	for(auto cu:s1)cc[cu]=0;
	for(auto cu:s2)cc[cu]=0;
	int n1=s1.size(),n2=s2.size();
	if(zh!=1ll*n1*(n1-1)+1ll*n2*(n2-1))return 0;
	for(auto cu:vc)a1[cu]=a2[cu]=0;
	a1[x]=++tt,a2[x]=++tt;
	for(auto cu:s1)a1[cu]=a1[x];
	for(auto cu:s2)a1[cu]=a2[x];
	for(auto cu:s1)if(!ranse(cu))return 0;
	for(auto cu:s2)if(!ranse(cu))return 0;
	for(auto cu:vc){
		for(auto uc:g[cu]){
			if(a1[cu]!=a1[uc]){
				if(a1[cu]!=a2[uc]){
					if(a2[cu]!=a1[uc]){
						if(a2[cu]!=a2[uc]){
							return 0;
						}
					}
				}
			}
		}
	}
	return 1;
}
int bb[300005];
bool check(int x){
	vc.clear();
	getall(x);
	if((signed)vc.size()==1){
		a1[x]=++tt,a2[x]=++tt;
		return 1;
	}
	int p=g[x][0];
	vector<int>s1,s2;
	for(auto cu:g[x]){
		if(cu==p)s1.emplace_back(cu);
		else s2.emplace_back(cu);
	}
	if(test(x,vc,s1,s2))return 1;
	for(auto cu:g[x])++bb[cu];
	int q=0;
	for(auto cu:g[p]){
		if(bb[cu]){
			q=cu;
			break;
		}
	}
	for(auto cu:g[x])--bb[cu];
	if(!q)return 0;
	s1.clear(),s2.clear();
	for(auto cu:g[p])++bb[cu];
	for(auto cu:g[q])++bb[cu];
	for(auto cu:g[x]){
		if(cu==p||cu==q)s1.emplace_back(cu);
		else if(bb[cu]==2)s1.emplace_back(cu);
		else s2.emplace_back(cu);
	}
	for(auto cu:g[p])--bb[cu];
	for(auto cu:g[q])--bb[cu];
	if(test(x,vc,s1,s2))return 1;
	s1.clear(),s2.clear();
	int flag=1;
	for(auto cu:g[p])bb[cu]^=1;
	for(auto cu:g[q])bb[cu]^=2;
	for(auto cu:g[x]){
		if(cu==p)s1.emplace_back(cu);
		else if(cu==q)s2.emplace_back(cu);
		else if(bb[cu]==1)s1.emplace_back(cu);
		else if(bb[cu]==2)s2.emplace_back(cu);
		else{
			flag=0;
			break;
		}
	}
	for(auto cu:g[p])bb[cu]^=1;
	for(auto cu:g[q])bb[cu]^=2;
	if(!flag)return 0;
	if(test(x,vc,s1,s2))return 1;
	return 0;
}
int lg[600005];
int main(){
	int T;
	scanf("%d",&T);
	while(T--){
		int n,m;
		scanf("%d%d",&n,&m);
		for(int i=1;i<=n;++i)g[i].clear();
		for(int i=1;i<=m;++i){
			int u,v;
			scanf("%d%d",&u,&v);
			g[u].emplace_back(v);
			g[v].emplace_back(u);
		}
		for(int i=1;i<=n;++i)vist[i]=0;
		tt=0;
		int flag=1;
		for(int i=1;i<=n;++i)if(!vist[i]){
			if(!check(i)){
				flag=0;
				break;
			}
		}
		if(T>61166)continue;
		if(!flag)puts("No");
		else{
			puts("Yes");
			int l=0;
			for(int i=1;i<=n;++i){
				lg[++l]=a1[i],lg[++l]=a2[i];
			}
			sort(lg+1,lg+l+1);
			l=unique(lg+1,lg+l+1)-lg-1;
			printf("%d %d\n",l,n);
			for(int i=1;i<=n;++i){
				int A1=lower_bound(lg+1,lg+l+1,a1[i])-lg;
				int A2=lower_bound(lg+1,lg+l+1,a2[i])-lg;
				printf("%d %d\n",A1,A2);
			}
		}
	}
	return 0;
}