#include <bits/stdc++.h>
#define SIZE 300005
#define MX 3000005
using namespace std;
typedef pair <int,int> P;

vector <P> vec[SIZE];
int col[MX];
set <P> edge;
bool use[SIZE];
int now_sz;
bool clique(vector <int> nd){
	for(int i=0;i<nd.size();i++){
		for(int j=i+1;j<nd.size();j++){
			int a=nd[i],b=nd[j];
			if(a>b) swap(a,b);
			if(edge.find(P(a,b))==edge.end()) return false;
		}
	}
	return true;
}
bool cur[SIZE];
bool labelling(vector <int> nd,int now){
	for(int i=0;i<nd.size();i++) cur[nd[i]]=true;
	bool up=true;
	for(int i=0;i<nd.size();i++){
		int v=nd[i];
		for(int j=0;j<vec[v].size();j++){
			int to=vec[v][i].first,id=vec[v][i].second;
			if(cur[to]){
				if(col[id]!=-1) up=false;
				col[id]=now;
			}
		}
	}
	for(int i=0;i<nd.size();i++) cur[nd[i]]=false;
	return up;
}
bool dfs(vector <int>nd);
bool check_vertex(int v);
int now_col;
bool dfs(vector <int> nd){
	if(!clique(nd)) return false;
	if(!labelling(nd,now_col++)) return false;
	for(int i=0;i<nd.size();i++){
		int v=nd[i];
		if(!check_vertex(v)) return false;
	}
	return true;
}
bool check_vertex(int v){
	int s=-1;
	vector <int> nd;
	for(int i=0;i<vec[v].size();i++){
		int to=vec[v][i].first,id=vec[v][i].second;
		if(col[id]!=-1){
			if(s!=-1&&s!=col[id]) return false;
			s=col[id];
		} else{
			nd.push_back(to);
		}
	}
	if(!nd.empty()){
		nd.push_back(v);
		if(!dfs(nd)) return false;
	}
	return true;
}
bool start(vector <int> nd){
	int v=nd[0];
	int f=now_col;
	queue <int> que;
	que.push(v);
	use[v]=true;
	vector <int> all;
	while(!que.empty()){
		v=que.front();que.pop();
		all.push_back(v);
		for(int i=0;i<vec[v].size();i++){
			int to=vec[v][i].first,id=vec[v][i].second;
			col[id]=-1;
			if(!use[to]){
				que.push(to);
				use[to]=true;
			}
		}
	}
	if(!dfs(nd)){
		now_col=f;
		for(int i=0;i<all.size();i++) use[all[i]]=false;
		return false;
	}
	return true;
}
bool run(int v){
	if(vec[v].size()<=4){
		for(int S=0;S<1<<vec[v].size();S++){
			if(!(S>>0&1)) continue;
			vector <int> nd;
			nd.push_back(v);
			for(int i=0;i<vec[v].size();i++){
				if(S>>i&1){
					nd.push_back(vec[v][i].first);
				}
			}
			if(start(nd)){
				return true;
			}
		}
		return false;
	}
	int m=5;
	vector <int> mx;
	for(int S=0;S<1<<m;S++){
		vector <int> nd;
		for(int i=0;i<m;i++){
			if(S>>i&1){
				nd.push_back(vec[v][i].first);
			}
		}
		if(mx.size()<nd.size()&&clique(nd)){
			mx=nd;
		}
	}
	if(mx.size()<=2) return false;
	vector <int> one=mx;
	one.push_back(v);
	for(int i=m;i<vec[v].size();i++){
		int to=vec[v][i].first;
		vector <int> nd=mx;
		nd.push_back(to);
		if(clique(nd)){
			one.push_back(to);
		}
	}
	return start(one);
}
void solve(){
	int n,m;
	scanf("%d%d",&n,&m);
	for(int i=0;i<n;i++) vec[i].clear();
	edge.clear();
	for(int i=0;i<m;i++){
		int u,v;
		scanf("%d%d",&u,&v);u--,v--;
		vec[u].push_back(P(v,i));
		vec[v].push_back(P(u,i));
		edge.insert(P(min(u,v),max(u,v)));
	}
	for(int i=0;i<n;i++) use[i]=false;
	for(int i=0;i<m;i++) col[i]=-1;
	now_sz=0;
	now_col=0;
	for(int i=0;i<n;i++){
		if(use[i]) continue;
		if(!run(i)){
			puts("No");
			return;
		}
	}
	puts("Yes");
	vector <int> L(n),R(n);
	for(int i=0;i<n;i++){
		set <int> st;
		for(int j=0;j<vec[i].size();j++){
			int id=vec[i][j].second;
			if(col[id]!=-1) st.insert(col[id]);
		}
		assert(st.size()<=2);
		while(st.size()<=2){
			st.insert(now_col++);
		}
		set <int>::iterator it=st.begin();
		L[i]=*it;
		R[i]=*(++it);
	}
	printf("%d %d\n",now_col,n);
	for(int i=0;i<n;i++) printf("%d %d\n",L[i]+1,R[i]+1);
}
int main(){
	int T;
	scanf("%d",&T);
	while(T--) solve();
}