#include<bits/stdc++.h>
#define N 300010
using namespace std;
int T,a,b,n,m,k,ans[N],f[N];
vector <int> q[N],l[N];
int main()
{
	cin >> T;
	while(T --)
	{
		cin >> n >> m >> k;
		memset(f,0,sizeof(f));
		for(int i = 1;i <= m;i ++)
		{
			cin >> a >> b;
			q[a].push_back(b);
			l[a].push_back(1);
			ans[i] = a;
		}
		queue <int> qu;
		qu.push(1);
		bool e = 1;
		while(!qu.empty())
		{
			int x = qu.front();
			qu.pop();
			for(int i = 0;i < q[x].size();i ++)
			{
				int v = q[x][i];
//				cout << v << ' ' << f[v] << ' ' << l[x][i] << endl;
				if(!f[v])
				{
					f[v] = f[x] + 1;
					qu.push(v);
				}
				else
				{
					l[x][i] = f[v] - f[x] + 1;
					if(l[x][i] < 1) l[x][i] = 1;
					if(l[x][i] > k)
					{
						cout << "No\n";
						e = 0;
						break;
					}
				}
			}
			if(!e) break;
		}
		if(!e) continue;
		cout << "Yes\n";
		for(int i = 1;i <= m;i ++)
		{
			a = ans[i];
			cout << l[a][0] << ' ';
			l[a].erase(l[a].begin());
		}
		cout << endl;
		for(int i = 1;i <= n;i ++)
			q[i].clear(),l[a].clear();
	}
	return 0;
}