← 返回题目列表

Codeforces · 1346/D

D. 建造地牢

中文机器翻译题面 查看原题

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