#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
#define int long long
const int N=5e5+5;
struct node{
	int go,ti;
};
struct node1{
	int id,v;
	bool operator<(const node1 &A)const{
		return A.v<v;
	}
};
vector<node>edge[N];
bool vis[N];
int dis[N],ans[N];
int T,n,k,m,f,t;
void dijkstra(int st,int op){
	priority_queue<node1>q;
	memset(dis,0x7f,sizeof(dis));
	memset(vis,0,sizeof(vis));
	for(int i=1;i<=n;i++){
		edge[i].clear();
	}
	fill(ans+1,ans+1+m,1);
	int maxn=0;
	dis[st]=0;
	q.push(node1{st,0});
	while(!q.empty()){
		int u=q.top().id;
		q.pop();
		if(vis[u]){
			continue;
		}
		vis[u]=1;
		for(int i=0;i<edge[u].size();i++){
			int v=edge[u][i].go,id=edge[u][i].ti;
			if(dis[v]>dis[u]+1){
				dis[v]=dis[u]+1;
				q.push(node1{v,dis[v]});
			}
			else if(dis[v]==dis[u]+1){
				ans[id]++;
				maxn=max(maxn,ans[id]);
			}
		}
	}
	if(maxn>op){
		cout<<"No"<<endl;
	}
	else{
		cout<<"Yes"<<endl;
		for(int i=1;i<=m;i++){
			cout<<ans[i]<<" "; 
		}
		cout<<endl;
	}
	return ;
}
signed main(){
	//freopen("string.in","r",stdin);
	//freopen("string.out","w",stdout);
	ios::sync_with_stdio(0);
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout.flush();
	cin>>T;
	while(T--){
		cin>>n>>m>>k;
		for(int i=1;i<=m;i++){
			cin>>f>>t;
			edge[f].push_back(node{t,i});
		}
		dijkstra(1,k);
	}
	return 0;
}