410569: GYM104053 C Customs Controls 2

Look how short the statement is! This must be the easiest problem.

Given a directed acyclic graph $$$G$$$, you need to assign each vertex $$$i$$$ a positive integer weight $$$w_i$$$. Your goal is to make all paths from $$$1$$$ to $$$n$$$ of equal length.

A directed acyclic graph is a graph with directed edges and without cycles.

The length of a path is defined as the sum of the weights of vertices on the path.

The first line contains a positive integer $$$T$$$ ($$$1\le T\le 10^4$$$), denoting the number of test cases.

For each testcase:

• The first line contains two integers $$$n, m$$$ ($$$1\le n\le 2\cdot 10^5$$$, $$$1\le m\le 5\cdot 10^5$$$), denoting the number of vertices and edges.
• The next $$$m$$$ lines each contains two integers $$$u$$$, $$$v$$$, denoting an edge from $$$u$$$ to $$$v$$$.

It is guaranteed that $$$\sum n\le 2\cdot 10^5$$$, $$$\sum m\le 5\cdot 10^5$$$.

It is guaranteed that the graph contains no multiple edges, no self-loops and no cycles. It is also guaranteed that every vertex is reachable from $$$1$$$ and can reach $$$n$$$.

For each testcase, if there is no solution, then output "No" on a single line. Otherwise, output "Yes" on the first line, then $$$n$$$ positive integers $$$w_1,w_2,\ldots,w_n$$$ ($$$1\le w_i\le 10^9$$$) on the second line.

2
3 3
1 2
1 3
2 3
8 9
1 2
1 3
1 4
2 5
3 6
4 7
5 8
6 8
7 8

No
Yes
1 1 2 3 3 2 1 1

2
11 16
1 2
1 3
1 4
1 5
2 6
4 6
3 7
4 7
5 8
6 8
2 9
3 9
7 10
8 10
9 11
10 11
8 10
1 2
1 3
2 4
3 5
3 6
4 6
2 7
5 7
6 8
7 8

Yes
1 1 1 1 2 1 2 1 3 1 1
No