#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn=3e5+5;
int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
	return x*f;
}
struct node{
	int to,id;
};
vector <node> a[maxn*2];
int T,n,m,k,dis[maxn],vis[maxn],ans[maxn],mx=-1e9;
priority_queue<pair<int,int>,vector<pair<int,int> > ,greater<pair<int,int> > > q;
bool dijkstra(int s){
	memset(dis,0x3f,sizeof(dis));
	dis[s]=0;
	mx=-1e9;
	q.push(make_pair(s,0));
	while(!q.empty()){
		int u=q.top().first;
		q.pop();
		if(vis[u]==T+10) continue;
		vis[u]=T+10;
		for(int i=0;i<a[u].size();i++){
			int v=a[u][i].to,w=1;
			int tmp=a[u][i].id;
			if(dis[v]>dis[u]+w){
				dis[v]=dis[u]+w;
				q.push(make_pair(v,dis[v]));
			}else if(dis[v]==dis[u]+w){
				//cout<<ans[tmp]<<endl;
				mx=max(mx,++ans[tmp]);
			}
		}
	}
	return mx<=k;
}
signed main(){
	T=read();
	while(T--){
		n=read(),m=read(),k=read();
		for(int i=1;i<=n;i++){
			a[i].clear();
		}
		for(int i=1;i<=m;i++){
			int x,y;
			x=read(),y=read();
			a[x].push_back(node{y,i});
		}
		
		for(int i=1;i<=m;i++){
			ans[i]=1;
		}
		if(dijkstra(1)==0){
			printf("No\n");
			continue;
		}else{
			printf("Yes\n");
			for(int i=1;i<=m;i++)cout<<ans[i]<<" \n"[i==m];
		}
	}
	return 0;
}