Bob has a connected undirected edge-weighted graph with ~n~ vertices and ~m~ edges. There are no self-loops in this graph, but there can be multiple edges between some pairs of vertices.

Alice told Bob the following about this graph:

• The edge weights are distinct integers from the range ~[1, m]~. In other words, they form some permutation of integers from ~1~ to ~m~.
• The weight of the ~i~-th edge is from the range ~[l_i , r_i]~ for each ~i~ from ~1~ to ~m~.
• The edges with indices ~1, 2, \dots, n - 1~ (the first ~n - 1~ edges in the input) form a minimum spanning tree of this graph.

Bob wants to know if it is possible. Determine if there exist such assignments of edge weights for which these conditions hold and if yes, find any of them.

Input Format

The first line contains a single integer ~t~ (~1 \le t \le 10^5~), the number of test cases. The description of test cases follows.

The first line of each test case contains two integers ~n~ and ~m~ (~1 \le n - 1 \le m \le 5 \times 10^5~), the number of vertices and the number of edges, respectively.

The ~i~-th of the following ~m~ lines contains four integers ~u_i~, ~v_i~, ~l_i~, ~r_i~ (~1 \le u < v \le n~, ~1 \le l_i \le r_i \le m~), indicating that there is an edge connecting vertices ~u_i~, ~v_i~, and that its weight should be in range ~[l_i, r_i]~.

It's guaranteed that for each test case, edges with indices ~1, 2, \dots , n - 1~ form a spanning tree of the given graph.

It's guaranteed the sum of ~m~ over all test cases doesn't exceed ~5 \times 10^5~.

Output Format

For each test case, if an array of edge weights that satisfy the conditions doesn't exist, output NO in the first line.

Otherwise, in the first line, output YES. In the second line output ~m~ integers ~w_1 ,w_2 , \dots ,w_m~ (~1 \le w_i \le m~, all ~w_i~ are distinct), the edge weights (where ~w_i~ is the weight assigned to the ~i~-th edge in the input).

If there are multiple answers, output any of them.

Constraints

Subtask	Points	Additional constraints
~1~	~4~	~l_i = r_i~ (~1 \le i \le m~)
~2~	~6~	The sum of ~m~ over all test cases doesn't exceed ~10~
~3~	~10~	The sum of ~m~ over all test cases doesn't exceed ~20~
~4~	~10~	~m = n - 1~, the sum of ~m~ over all test cases doesn't exceed ~500~
~5~	~7~	~m = n - 1~
~6~	~20~	~m = n~
~7~	~11~	The sum of ~m~ over all test cases doesn't exceed ~5000~
~8~	~8~	~u_i = i~, ~v_i = i + 1~ (~1 \le i \le n - 1~)
~9~	~12~	The sum of ~m~ over all test cases doesn't exceed ~10^5~
~10~	~12~	No additional constraints

Sample Input

3
4 6
1 2 1 3
1 3 2 6
3 4 1 2
1 4 2 5
2 3 2 4
2 4 4 6
4 4
1 2 2 2
2 3 3 3
3 4 4 4
1 4 1 4
5 6
1 2 1 1
2 3 1 2
3 4 2 4
4 5 6 6
1 4 4 6
1 4 5 6

Sample Output

YES
2 3 1 5 4 6
NO
YES
1 2 3 6 4 5