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

你的朋友告诉你关于该图的以下信息： 边权是范围 $[1, m]$ 内的互不相同的整数。换句话说，它们构成了 $1$ 到 $m$ 的一个排列。 对于每个 $i$（$1 \le i \le m$），第 $i$ 条边的权重在范围 $[l_i, r_i]$ 内。 * 索引为 $1, 2, \dots, n-1$ 的边（输入中的前 $n-1$ 条边）构成了该图的一棵最小生成树。

你需要判断这是否可能。确定是否存在满足这些条件的边权分配方案，如果存在，请找出其中任意一种。

作为提醒，图的生成树是该图的任意一个构成树（包含 $n$ 个顶点和 $n-1$ 条边的连通图）的边子集。图的最小生成树是该图所有生成树中权重之和最小的生成树。

输入格式

第一行包含一个整数 $t$ ($1 \le t \le 10^5$)，表示测试用例的数量。接下来是各测试用例的描述。

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

接下来的 $m$ 行中，第 $i$ 行包含四个整数 $u_i, v_i, l_i, r_i$ ($1 \le u_i < v_i \le n, 1 \le l_i \le r_i \le m$)，表示存在一条连接顶点 $u_i$ 和 $v_i$ 的边，且其权重应在范围 $[l_i, r_i]$ 内。

保证对于每个测试用例，索引为 $1, 2, \dots, n-1$ 的边构成了给定图的一棵生成树。

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

输出格式

对于每个测试用例，如果不存在满足条件的边权数组，则在第一行输出 "NO"。

否则，在第一行输出 "YES"。在第二行输出 $m$ 个整数 $w_1, w_2, \dots, w_m$ ($1 \le w_i \le m$，且所有 $w_i$ 互不相同)，表示分配给输入中第 $i$ 条边的权重。

如果存在多个答案，输出其中任意一个即可。

你可以以任意大小写形式输出字母（例如，"YES", "Yes", "yes", "yEs", "yES" 均会被识别为肯定回答）。

样例

输入 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. (4 分): $l_i = r_i$ ($1 \le i \le 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 分): $u_i = i, v_i = i + 1$ ($1 \le i \le n - 1$)
9. (12 分): 所有测试用例的 $m$ 之和不超过 $10^5$
10. (12 分): 无额外限制