Background

As a Luogu internet celebrity, Fan Ju has many passionate fans, and he also really enjoys meeting up in person, searching for his fans all over the country.

Problem Description

The map of Fan Ju's hometown is a directed graph with $n$ nodes and $m$ directed roads. Each node is a city. Fan Ju is in city $1$, and city $1$ can always reach any other city through some roads.

The $i$-th road goes from city $x_i$ to city $y_i$ with length $z_i$.

Now Fan Fan wants to travel from his city $1$ to every city to meet fans in person.

Since Fan Fan is skilled at the SPFA algorithm, during these meetups he will naturally go to other cities along the shortest paths in terms of total length.

However, Fan Fan has trouble making choices. He hopes that the shortest path from city $1$ to every city is unique, so he decides to cast magic to change the lengths of all roads. Specifically:

After casting magic, the length of each road can be changed independently into an integer in the range $[1,k]$, where $k$ is Fan Ju's magic level.

But the map of his world and his magic level keep changing. In total there will be $T$ changes, so he wants you to give a construction method for each of the $T$ queries so that Fan Ju will not be troubled by choices, or report that there is no solution.

Input Format

The first line contains an integer $T$, the number of test cases.

Then for each of the $T$ test cases, the first line contains three integers $n,m,k$, followed by $m$ lines describing directed roads $(x_i,y_i)$.

Self-loops and multiple edges are not guaranteed to be absent.

Output Format

For each test case, if there is a solution, output Yes on the first line, and output $m$ numbers on the second line as the weights of the edges in order. If there is no solution, output No on a single line.

This problem uses special judge, meaning if there are multiple valid answers, you may output any one of them.

2
3 2 3
1 2
2 3
2 2 1
1 2
1 2

Yes
1 2
No

Hint

Sample Explanation

For the first test case, the path from node $1$ to every node is unique, so no matter how the edge weights are set, the shortest paths are unique.

For the second test case, since $k=1$, both edges can only be set to weight $1$. The shortest path length from node $1$ to node $2$ is $1$, and you can take either of the two edges, so it is not unique.

Constraints

This problem uses bundled testdata.

For $20\%$ of the testdata, $n,m\leq 5$.

For another $20\%$ of the testdata, $k=1$.

For another $20\%$ of the testdata, $m=n-1$.

For another $20\%$ of the testdata, $k=10^9$.

For $100\%$ of the testdata, $n\ge 1$, $m\ge 0$, $1\le \sum n,\sum m\leq 3\times 10^5$, $1\leq k \leq 10^9$, and $1\le x_i,y_i\le n$.

Translated by ChatGPT 5