Description

给定一个含有 $n$ 个顶点和 $m$ 条边的连通无向带权图。该图中没有自环（即不存在一条边连接同一个顶点），但某些顶点对之间可能存在多条边。

你的朋友告诉你关于该图的如下信息：

• 所有边权值是范围 $[1, m]$ 内的互不相同的整数。换句话说，它们构成了 $1$ 到 $m$ 的一个排列。
• 第 $i$ 条边的权值必须落在区间 $[l_i, r_i]$ 内（对每个 $1 \leq i \leq m$）。
• 输入中的前 $n-1$ 条边（即边编号 $1, 2, \ldots, n-1$）必须构成该图的最小生成树。

你需要判断这些条件是否有可能同时满足。如果可能，请构造出任意一组符合条件的边权赋值。

回顾一下，生成树是该图的一个边集，包含 $n-1$ 条边，能使图连通并且无环。最小生成树是指所有生成树中边权和最小的那一棵。

Input Format

第一行包含一个整数 $t$（$1 \leq t \leq 10^5$），表示测试用例的个数。接下来依次给出 $t$ 个测试用例。

每个测试用例的第一行包含两个整数 $n$ 和 $m$（$1 \leq n-1 \leq m \leq 5 \cdot 10^5$），分别表示顶点数和边数。

接下来 $m$ 行中，第 $i$ 行包含四个整数 $u_i, v_i, l_i, r_i$（$1 \leq u_i < v_i \leq n,\ 1 \leq l_i \leq r_i \leq m$），表示顶点 $u_i$ 和 $v_i$ 之间有一条边，其权值必须在区间 $[l_i, r_i]$ 内。

保证对于每个测试用例，编号为 $1, 2, \ldots, n-1$ 的边构成一棵生成树。

保证所有测试用例中 $m$ 的总和不超过 $5 \cdot 10^5$。

Output Format

对于每个测试用例：

• 如果不存在符合条件的权值赋值方案，则输出一行 "NO"。
• 否则，输出一行 "YES"，并在下一行输出 $m$ 个整数 $w_1, w_2, \ldots, w_m$（$1 \leq w_i \leq m$，互不相同），其中 $w_i$ 表示赋予第 $i$ 条边的权值。

如果存在多个解，输出任意一个即可。

输出时字母大小写不敏感（例如 "YES", "Yes", "yes", "yEs" 都视为正确）。

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

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

Hint

评分规则

1. （4 分）：所有 $l_i = r_i$（$1 \leq i \leq m$）
2. （6 分）：所有测试用例中 $m$ 的总和不超过 $10$
3. （10 分）：所有测试用例中 $m$ 的总和不超过 $20$
4. （10 分）：$m = n - 1$ 且所有测试用例中 $m$ 的总和不超过 $500$
5. （7 分）：$m = n - 1$
6. （20 分）：$m = n$
7. （11 分）：所有测试用例中 $m$ 的总和不超过 $5000$
8. （8 分）：对于所有 $1 \leq i \leq n-1$，$u_i = i,\ v_i = i + 1$
9. （12 分）：所有测试用例中 $m$ 的总和不超过 $10^5$
10. （12 分）：无额外限制

翻译由 ChatGPT-5 完成