Description

Volodya 梦想成为一名侦探。因此，Volodya 经常阅读讲述破案传奇的书籍。在研究下一个案件时，Volodya 发现了调查过程中的一些有趣细节。

本案共有 $n$ 名嫌疑人。证据板上包含了全部 $n$ 个人。最初，嫌疑人之间没有任何联系。

在调查过程中，嫌疑人之间逐渐出现了新的联系。每一条新联系都连接了此前尚未直接或间接（通过其他人）相连的两个人。

让我们来看一下当 $A$ 和 $B$ 之间出现一条联系时的情况。除了涉及的两个人名字外，每条联系还包含三个参数：$c_A$ —— 针对 $A$ 的证据强度，$c_B$ —— 针对 $B$ 的证据强度，$w_{AB}$ —— 这条联系的总证据强度。出于自然原因，联系的证据强度不能超过针对 $A$ 和 $B$ 的证据强度之和。也就是说，对于每一条联系，一定有 $w_{AB} \leq c_A + c_B$。侦探们在获得这样一条联系时，会在证据板上将 $A$ 和 $B$ 的照片之间画一条线，并将 $w_{AB}$ 标注在这条线上。同时，会在 $A$ 的照片上贴上写有 $c_A$ 的便签，在 $B$ 的照片上贴上写有 $c_B$ 的便签。如果照片上已经有其他便签，则新便签会贴在旧便签之上。

案件正是在所有嫌疑人通过 $n-1$ 条联系连通时被侦破的。破案后，证据板以原貌被陈列在博物馆中。

受到这种方式的启发，Volodya 参观了博物馆，并详细研究了这块证据板。Volodya 注意到，对于每个人 $v$，其照片上从上到下贴有编号为 $c_{v,1}, \ldots, c_{v,deg_v}$ 的便签。这里 $deg_v$ 表示与 $v$ 相关的联系数量。同时，Volodya 记得第 $i$ 条联系发生在 $a_i$ 和 $b_i$ 之间，证据强度为 $w_i$。不幸的是，这些联系的编号是随意的，并不一定与它们在调查中出现的先后顺序一致。

由于联系编号的混乱，证据板上的信息无法帮助还原调查过程。现在 Volodya 需要你帮助他还原一种可能的、侦探们获得这些联系的时间顺序。如果不存在符合条件的顺序，也有可能是博物馆伪造了信息。

Input Format

输入的第一行包含两个整数 $n$ 和 $g$（$2 \le n \le 200\,000$，$0 \le g \le 9$），分别表示案件中的嫌疑人数和测试组编号。

接下来 $n-1$ 行描述每一条联系。第 $i$ 行包含三个整数 $a_i$、$b_i$、$w_i$（$1 \le a_i, b_i \le n$，$1 \le w_i \le 10^9$，$a_i \neq b_i$），表示第 $i$ 条联系连接了 $a_i$ 和 $b_i$，证据强度为 $w_i$。保证所有嫌疑人最终连通。

接下来 $n$ 行描述便签上的数字。第 $i$ 行包含 $deg_i$ 个整数 $c_{i, 1}, \ldots, c_{i, deg_i}$（$0 \le c_{i, j} \le 10^9$），表示第 $i$ 个人照片上从上到下的便签数字。$deg_i$ 等于与第 $i$ 个人相关的联系数量。

Output Format

如果不存在符合条件的还原顺序，输出一行 No（不含引号）。

否则，第一行输出 Yes（不含引号）。第二行输出 $n-1$ 个数字，表示一种符合条件的联系出现顺序。联系编号为 $1$ 到 $n-1$，顺序与输入一致。如果存在多种可能的顺序，输出任意一种均可。

5 0
1 2 3
1 3 1
3 4 12
3 5 6
0 4
2
6 1 3
8
3

Yes
1 4 2 3

7 0
1 2 4
2 3 4
3 4 4
4 5 4
5 6 4
6 7 4
2
1 2
2 3
1 2
3 2
1 2
179

Yes
5 1 2 3 6 4

4 0
1 2 7
1 3 6
1 4 5
3 2 1
5
4
3

No

Hint

说明

在第一个样例中，可能的顺序之一为 $[1, 4, 2, 3]$。按时间顺序，第 $1$ 条联系连接了 $A=1$ 和 $B=2$，$c_A=4, c_B=2, w_{AB}=3$，$3 \leq 2+4$，证据合理。第 $2$ 条联系连接了 $A=3$ 和 $B=5$，$c_A=3, c_B=3, w_{AB}=6$，$6 \leq 3+3$，证据合理。第 $3$ 条联系连接了 $A=1$ 和 $B=3$，$c_A=0, c_B=1, w_{AB}=1$，$1 \leq 0+1$，证据合理。第 $4$ 条联系连接了 $A=3$ 和 $B=4$，$c_A=6, c_B=8, w_{AB}=12$，$12 \leq 6+8$，证据合理。参见下图更易理解。

:::align{center} :::

计分方式

本题共九组测试。只有通过该组及其所有依赖组全部测试，才能获得该组分数。请注意，部分组无需通过样例测试。Offline-evaluation 表示该组的结果仅在比赛结束后可见。

翻译由 ChatGPT-4.1 完成。