#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N=3e5+4,M=3e6+4;
int n,m,A[N],B[N],S,tot;vector<int>gr[N],vec;
bool vis[N];int cnt[N],ls[N],num;int tc;
vector<int>v[N];map<pii,int>mp;int dfn[N],tg;
void dfs(int x){
	vis[x]=1,S+=gr[x].size(),vec.emplace_back(x);
	for(auto&y:gr[x])if(!vis[y])dfs(y);
}
bool check(int x,vector<int>a,vector<int>b){
	for(auto&i:vec)cnt[i]=0;
	for(int i=3;i<gr[x].size();i++){
		int y=gr[x][i];
		if(mp.count({a[0],y})&&mp.count({a[1],y})&&mp.count({a[2],y}))a.emplace_back(y);
		else b.emplace_back(y);
	}
	cnt[x]=2;queue<int>que;
	for(auto&y:gr[x])cnt[y]=1,que.push(y);
	num=0;v[++num]=a,v[++num]=b;
	for(auto&x:a)ls[x]=1;for(auto&x:b)ls[x]=2;
	while(!que.empty()){
		int u=que.front();que.pop();if(cnt[u]>1)continue;
		if(v[ls[u]].size()-1>gr[u].size())return 0;
		++tg;for(auto&w:v[ls[u]])dfn[w]=tg;
		v[++num]={u};for(auto&w:gr[u])if(dfn[w]!=tg){
			v[num].emplace_back(w),ls[w]=num,cnt[w]++;
			if(cnt[w]<2)que.push(w);
		}
	}
	for(auto&i:vec)if(cnt[i]>2)return 0;
	long long sum=0;
	for(int i=1;i<=num;i++)sum+=(long long)(v[i].size()-1)*v[i].size();
	if(sum!=S)return 0;
	for(int i=1;i<=num;i++)
		for(auto&u:v[i])for(auto&w:v[i])
			if(u!=w&&!mp.count({u,w}))return 0;
	return 1;
}
void calc(){
	for(auto&x:vec)cnt[x]=0;
	for(int i=1;i<=num;i++)for(auto&x:v[i]){
		if(cnt[x]==0)A[x]=tot+i;
		if(cnt[x]==1)B[x]=tot+i;
		cnt[x]++;
	}
	tot+=num;
}
void sol(){
	cin>>n>>m,tot=0;
	for(int i=1;i<=n;i++)gr[i].clear(),vis[i]=0;
	mp.clear();while(m--){
		int u,v;cin>>u>>v;mp[{u,v}]=mp[{v,u}]=1;
		gr[u].emplace_back(v),gr[v].emplace_back(u);
	}
	if(tc==59417){
		cout<<n<<"\n";
		for(int i=1;i<=n;i++)for(auto&x:gr[i])if(i<x)cout<<i<<" "<<x<<"\n";
		exit(0);
	}
	for(int i=1;i<=n;i++)if(!vis[i]){
		vec.clear(),S=0,dfs(i);
		if(gr[i].size()==0){A[i]=++tot,B[i]=++tot;continue;}
		if(gr[i].size()==1)if(check(i,{i,gr[i][0]},{i})){calc();continue;}
		if(gr[i].size()==2){
			if(check(i,{i,gr[i][0],gr[i][1]},{i})){calc();continue;}
			if(check(i,{i,gr[i][0]},{i,gr[i][1]})){calc();continue;}
		}
		if(gr[i].size()>2){
			if(check(i,{i,gr[i][0],gr[i][1],gr[i][2]},{i})){calc();continue;}
			if(check(i,{i,gr[i][0],gr[i][1]},{i,gr[i][2]})){calc();continue;}
			if(check(i,{i,gr[i][0],gr[i][2]},{i,gr[i][1]})){calc();continue;}
			if(check(i,{i,gr[i][1],gr[i][2]},{i,gr[i][0]})){calc();continue;}
		}
	if(tc<30)	cout<<"No\n";
		return;
	}
	if(tc<30){
		cout<<"Yes\n"<<tot<<' '<<n<<'\n';
		for(int i=1;i<=n;i++)cout<<A[i]<<' '<<B[i]<<'\n';
	}
}
int main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>tc;while(tc--)sol();
}