← 返回题目列表

Codeforces · 830/E

E. 永动机

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

开发者 Petr 认为他发明了永动机。也就是说,他有很多元素,它们按以下方式工作。

每个元素都有一个控制器,可以设置为任何非负实数值。如果控制器设置为某个值 x,则控制器每秒消耗 x2 能量单位。同时,通过电线连接的任何两个元件每秒产生 y·z 能量单位,其中 y 和 z 是其控制器上设置的值。

Petr 只有有限数量的电线,因此他已经构建了一些元件和电线的方案,现在他感兴趣的是是否可以设置控制器,使系统产生的功率至少与其消耗的功率相同,并且至少将一个控制器设置为不为 0 的值。帮助他检查这一点,如果可能的话,找到应设置的所需整数值。

保证如果存在满足上述条件的控制器设置,则存在所需的不大于106的整数值。

输入

输入中有多个(至少一个)测试用例。第一行包含单个整数——测试用例的数量。

每个测试用例之前都有一个空行。测试用例的第一行包含两个整数 n 和 m (1 ≤ n ≤ 105, 0 ≤ m ≤ 105) - 方案中的元素数量和电线数量。

之后是 m 行,每行包含两个整数 a 和 b (1 ≤ a, b ≤ n)——通过电线连接的两个元素。没有任何元素与其自身相连,没有两个元素通过多于一根的电线连接。

保证所有测试用例的n之和与m之和不超过105。

对于 hacks,您只能使用一个测试用例进行测试。

输出

打印每个测试用例的答案。

对于每个测试用例,如果可以将控制器设置为消耗的功率不大于产生的功率以及下一行所需的值,则打印“YES”。设置应为 0 到 106(含)之间的整数,并且至少有一个值应不同于 0。如果有多个答案,请打印其中任何一个。

如果无法按要求的方式设置控制器,请打印一行“NO”。

示例

输入 #1

4
4 4
1 2
2 3
3 4
4 2
3 2
2 3
3 1
4 6
1 2
3 4
4 2
1 4
1 3
3 2
10 9
2 1
3 2
5 2
6 2
2 7
2 8
2 9
2 10
4 2

输出 #1

YES
1 2 2 1
NO
YES
1 1 1 1
YES
1 5 1 1 1 1 1 1 1 1

注意

在第一个示例中,可以按照所需的方式设置控制器,例如,按照以下方式:在第一个元素上设置 1,在第二个和第三个元素上设置 2,在第四个元素上设置 1。消耗的功率等于每秒 12 + 22 + 22 + 12 = 10 个能量单位,产生的功率等于每秒 1·2 + 2·2 + 2·1 + 2·1 = 10 个能量单位。因此答案是“是”。

在第二个测试用例中,无法以所需的方式设置控制器。例如,如果我们将所有控制器设置为 0.5,则消耗的功率等于每秒 0.75 个能量单位,而产生的功率等于每秒 0.5 个能量单位。