Unique Shortest Paths via Magic Weights

In this problem, you are given a directed graph with (n) nodes and (m) directed edges. Each node represents a city, and city (1) is the starting point. It is guaranteed that from city (1) every other city is reachable via some sequence of directed roads.

Each edge (i) goes from city (x_i) to city (y_i) (with an original length (z_i), which will be ignored) and after applying magic, you can independently reassign its length to any integer in the range ([1,k]), where (k) is the magic level.

FanFan wants to travel from city (1) to every other city by always taking the shortest route. However, he is very indecisive, and he wants these shortest paths to be unique. To ensure uniqueness, you must reassign weights so that for every vertex (v), the shortest path from city (1) (taken according to your construction) is unique. In other words, if you decide on a particular spanning tree (of reachable vertices) with tree edges assigned a weight of (1), then for every other (non–tree) edge from (u) to (v), you must assign it a weight (w) (with (w \in [1,k])) that satisfies [ d(u)+ w > d(v), ] where (d(v)) is the distance (number of edges) from city (1) to (v) in the tree. A natural assignment is to set the weight for each non–tree edge to (\max(1, d(v)-d(u)+1)). If for any edge this value exceeds (k), then no valid assignment exists.

You are given (T) test cases. For each test case, if a valid assignment exists, output "YES" and then a line with (m) integers: the reassigned weights for the roads in the order they appear in the input. Otherwise, output "NO".

Input Format:

• \(T\) \(\rightarrow\) the number of test cases.
• For each test case:
  • A line containing three integers \(n\), \(m\), and \(k\).
  • Then \(m\) lines follow, each containing three integers \(x_i\), \(y_i\), and \(z_i\). (Note: \(z_i\) is given but will not affect your assignment.)

Output Format:

• For each test case, if a solution exists, first output a line containing "YES" and then a line with \(m\) space‐separated integers: the new lengths for each road in the same order as input.
• If no valid assignment exists, output a single line with "NO".

Constraints and Details:

• You must use the magic to reassign each road's length in the range \([1,k]\) independently.
• The starting city is \(1\) and it is guaranteed that there is a path from city \(1\) to every other city.
• If \(k=1\), then note that the only possible weight is \(1\), so a valid assignment exists only if the graph is already a tree (i.e. \(m = n-1\)).

inputFormat

The input begins with an integer (T) denoting the number of test cases. For each test case, the first line contains three integers (n), (m), (k). The following (m) lines each contain three integers (x_i), (y_i), and (z_i) representing an edge from city (x_i) to city (y_i) with original length (z_i).

outputFormat

For each test case, if a valid reassignment exists, output "YES" on a line, followed by a line with (m) space-separated integers representing the newly assigned road lengths (in the order of input). If no valid assignment exists, output a single line with "NO".

sample

3
3 3 2
1 2 5
2 3 7
1 3 10
3 2 1
1 2 3
2 3 4
4 5 3
1 2 2
1 3 4
2 3 1
2 4 3
3 4 6

NO
YES
1 1
YES
1 1 1 1 2