P13783 [eJOI 2022] Bounded Spanning Tree

给定一个含有 $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$ 条边，能使图连通并且无环。最小生成树是指所有生成树中边权和最小的那一棵。

第一行包含一个整数 $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$。

对于每个测试用例： - 如果不存在符合条件的权值赋值方案，则输出一行 `"NO"`。 - 否则，输出一行 `"YES"`，并在下一行输出 $m$ 个整数 $w_1, w_2, \ldots, w_m$（$1 \leq w_i \leq m$，互不相同），其中 $w_i$ 表示赋予第 $i$ 条边的权值。 如果存在多个解，输出任意一个即可。 输出时字母大小写不敏感（例如 `"YES"`, `"Yes"`, `"yes"`, `"yEs"` 都视为正确）。

### 评分规则 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 完成