Polycarp 正在开发一款 RPG 游戏,主角在地牢中与怪物战斗并寻找宝藏。现在波利卡普正在建造角色可以探索的地下城之一。
地牢由 $$$n$$$ 个房间组成,通过 $$$m$$$ 双向隧道连接,并且可以使用隧道从每个其他房间到达每个房间。房间由怪物看守(第 $$$i$$$ 个房间中的怪物数量为 $$$a_i$$$),隧道中有金币(第 $$$i$$$ 个隧道中的金币数量为 $$$w_i$$$)。第 $$$i$$$ 双向隧道连接房间 $$$v_i$$$ 和 $$$u_i$$$。
Polycarp已经确定了每个隧道中的硬币数量($$$w_i$$$的值已经已知),现在他尝试将怪物放置在房间中($$$a_i$$$的值尚不知道)。波利卡普想要选择每个房间中怪物的数量,以满足以下两个条件:
- 连接房间 $$$x$$$ 和 $$$y$$$ 的隧道的硬币数量应等于 $$$a_x$$$ 和 $$$a_y$$$ 中的最小值。也就是说,对于每个隧道 $$$i$$$,$$$w_i = \min (a_{v_i}, a_{u_i})$$$;
- 地牢中的怪物数量尽可能少。也就是说,$$$a_1 + a_2 + \dots + a_n$$$ 的值是可能的最小值。
帮助Polycarp选择值$$$a_1$$$、$$$a_2$$$、...、$$$a_n$$$,或者告诉他这是不可能的,他必须改变地牢计划中的某些内容。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 100000$$$) — 测试用例的数量。然后是测试用例。
每个测试用例的第一行包含两个整数 $$$n$$$ 和 $$$m$$$ ($$$2 \le n \le 200000$$$; $$$n - 1 \le m \le \min(200000, \frac{n(n-1)}{2})$$$) — 分别是地牢中的房间和隧道的数量。
接下来是 $$$m$$$ 行,每行描述地牢中的一条隧道。第 $$$i$$$ 行包含三个整数 $$$v_i$$$、$$$u_i$$$ 和 $$$w_i$$$ ($$$1 \le v_i, u_i \le n$$$; $$$v_i \ne u_i$$$; $$$1 \le w_i \le 10^9$$$) 表示连接房间的双向隧道$$$v_i$$$ 和 $$$u_i$$$,并包含 $$$w_i$$$ 硬币。隧道系统在每个测试用例中都是连接的(可以使用隧道从每个其他房间到达每个房间)。每对房间最多由一条隧道连接。
所有测试用例的 $$$n$$$ 总和不超过 $$$200000$$$。同样,所有测试用例的 $$$m$$$ 总和不超过 $$$200000$$$。
输出
对于每个测试用例,打印答案如下:
如果无法找到满足所有约束的 $$$a_1$$$、$$$a_2$$$、...、$$$a_n$$$ 的值,请在单独的行上打印一个字符串 NO。否则,在第一行打印 YES,并在第二行打印 $$$n$$$ 整数 $$$a_1$$$, $$$a_2$$$, ..., $$$a_n$$$。如果有多个有效答案,请打印其中任何一个。
示例
输入 #1
3 3 2 1 2 1 2 3 1 5 7 3 2 7 3 4 9 1 5 5 1 2 5 4 1 5 4 2 7 3 1 5 4 4 1 2 5 3 2 2 4 1 3 3 4 4
输出 #1
YES 1 1 1 YES 5 7 9 9 5 NO