题目描述

给定一个有 $n$ 个点、$m$ 条边的连通无向有边权图。图中没有自环，但是一些点对之间可能有重边。

关于这张图有如下信息：

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

请确定是否存在满足上述条件的一个边权分配方案，并且如果存在，找出一种方案。

输入格式

第一行一个整数 $t$，表示测试点个数。

每个测试点第一行包含两个整数 $n,m$，分别表示图的节点个数和边数。

接下来 $m$ 行，第 $i$ 行包含四个整数：

表示节点 $u_i,v_i$ 之间有一条边相连，这条边的边权应该在区间 $[l_i,r_i]$ 中。

保证：

保证对于每个测试点，下标为 $1,2,\ldots,n-1$ 的边会形成给定图的一棵生成树。

保证对于一组数据中的所有测试点，$m$ 的总和不超过 $5\times 10^5$。

输出格式

对于每个测试点，如果不存在满足条件的一组边权，第一行输出：

NO

否则，第一行输出：

YES

第二行输出 $m$ 个整数：

表示边权，其中 $w_i$ 表示赋给输入第 $i$ 条边的边权。这 $m$ 个整数应该两两不同，并且满足：

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

样例输入 #1

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

样例输出 #1

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

其余样例见下发文件。

数据范围

对于所有数据，保证：

保证对于每个测试点，下标为 $1,2,\ldots,n-1$ 的边会形成给定图的一棵生成树。

子任务

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