题目描述

题目译自 Open Olympiad in Informatics 2024 Day1 T2 「Доска улик / Evidence Board」。

案件有 $n$ 名嫌疑人，线索板初始无连接，后续陆续出现 $n-1$ 条线索，每条线索满足：

1. 连接两名此前无任何（直接/间接）联系的嫌疑人（即线索构成树结构）；
2. 含参数 $c_A$（A 的证据强度）、$c_B$（B 的证据强度）、$w_{AB}$（线索强度），且 $w_{AB} \leq c_A + c_B$；
3. 线索会在 A、B 图像贴对应 $c_A$、$c_B$ 的贴纸，新贴纸覆盖旧贴纸。

案件破解后，线索板状态如下：

• 保留 $n-1$ 条线索（编号混乱），每条线索记为 $(a_i, b_i, w_i)$；
• 每个嫌疑人 $v$ 有 $deg_v$ 张贴纸（$deg_v$ 为其关联线索数），从上到下为 $c_{v,1}, ..., c_{v,deg_v}$（对应线索出现时的贴纸，最后一张为最终覆盖的贴纸）。

需重建任意一种可能的线索出现时间顺序（线索编号 1~n-1），若不存在则输出 No。

输入格式

1. 第一行：两个整数 $n$ 和 $g$（$2 \leq n \leq 200000$，$0 \leq g \leq 9$），分别为嫌疑人数量和子任务编号；
2. 接下来 $n-1$ 行：每行三个整数 $a_i, b_i, w_i$（$1 \leq a_i, b_i \leq n$，$a_i \neq b_i$，$1 \leq w_i \leq 10^9$），表示第 $i$ 条线索的连接关系和强度；
3. 接下来 $n$ 行：第 $i$ 行含 $deg_i$ 个整数 $c_{i,1}, ..., c_{i,deg_i}$（$0 \leq c_{i,j} \leq 10^9$），表示嫌疑人 $i$ 的贴纸序列（$deg_i$ 为其关联线索数）。

输出格式

• 若存在合法顺序：第一行输出 Yes，第二行输出 $n-1$ 个整数（线索编号，按出现时间排序）；
• 若不存在：输出 No。

样例

样例 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

样例 2

输入

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

样例 3

输入

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

输出

No