失落的帝国

题目信息

时间限制: 2s

空间限制: 256M

输入文件: shi.in

输出文件: shi.out

题目描述

D 大陆上曾经有一个大一统帝国，帝国在 D 大陆修建了 $n$ 个城镇和 $m$ 条连接城镇的双向道路，第 $i$ 条道路连接城镇 $x_i$ 与 $y_i$，道路长度为 $w_i$，保证 $1\le w_i\le m$，且没有任何两条道路的长度相同。

经考古学家们的考证，第 $i$ 条道路的长度为 $[l_i, r_i]$ 中的整数，且编号在 $1, 2, \dots, n-1$ 的道路恰好构成连通帝国 $n$ 座城镇的最小生成树。现在，考古学家们需要利用计算机构造出可能的每条道路的长度，便于进一步研究。

请输出符合题意的每条边的长度的构造，或证明无解。

输入格式

本题包含多组数据，第一行包含一个整数 $T$，表示数据组数

对于每组数据，第一行包含两个整数 $n, m$，表示帝国的城镇数和道路数

接下来 $m$ 行，每行四个整数 $u_i, v_i, l_i, r_i$，表示一条道路的信息，含义如题所示

输出格式

对于每组测试数据，如果不存在合法的方案，输出一行一个字符串 NO

否则，先输出一行 YES，接下来一行包含 $m$ 个整数 $w_1, w_2, \cdots, w_m$，描述每条道路的长度。

样例

样例输入 1

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

样例输出 1

YES
3 8 5 2 1 6 10 9 7 4
YES
1 7 6 2 3 5 4 8 9
NO

数据范围

• 对于 $100 \%$ 的数据，$T \geq 1, 1 \leq n \leq 5 \times 10^5, 1 \leq m \leq 5 \times 10^5, 1 \leq u_i \leq v_i \leq n, 1 \leq l_i \leq r_i \leq m$
• 对于 $100 \%$ 的数据，每个测试点中，所有测试数据的 $m$ 的总和不超过 $5 \times 10^5$
• 对于 $100 \%$ 的数据，保证图为连通图，且前 $n-1$ 条边恰好构成原图的一棵生成树