「eJOI2022」Bounded Spanning Tree

题目描述

给定一个有 $n$ 个点 $m$ 条边的连通无向有边权图。图中没有自环（即，没有从一个点出发的边连向它本身），但是一些点对之间可能有重边。

你的朋友告诉了你关于这张图的如下信息：

1. 边权是在 $[1,m]$ 范围中互不相同的整数。换句话说，它们形成了整数 $1$ 到 $m$ 的某个排列。
2. 对于 $i$ 从 $1$ 到 $m$，第 $i$ 条边的边权在 $[l_i,r_i]$ 范围中。
3. 下标为 $1,2,\ldots,n-1$ 的边（输入中前 $n-1$ 条边）形成了这个图的一棵最小生成树。

你想要知道这是否是可能的。确定是否存在满足上述条件的一个边权分配方案，并且如果存在，找出一种方案。

注：图的一棵生成树是图上任何一个边的子集，这些边可以构成树（$n$ 个点 $n-1$ 条边的连通图）。图的最小生成树是图的所有生成树中边权和最小的生成树。

输入格式

第一行一个整数 $t$ ($1 \leq t \leq 10^5$)，表示测试点个数。对于每个测试点的描述如下。

每个测试点第一行包含两个整数 $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$ 条边的边权。这 $m$ 个整数应该两两不同。

如果有多组解，输出任意一组即可。

对于每个字母，你可以输出任何大小写情况。（例如，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

评分

详细子任务及附加限制如下表所示。

注：表中 $\sum m$ 指对于一组测试数据中所有测试点的 $m$ 之和。