给您一个无向图,其中每条边都有两种颜色之一:黑色或红色。
您的任务是为每个节点分配一个实数,以便:
- 对于每个黑色边缘,其端点处的值之和为 $$$1$$$;
- 对于每个红色边缘,其端点处的值之和为 $$$2$$$;
- 所有指定数字的绝对值之和尽可能最小。
否则,如果不可能,则报告没有可行的号码分配。
输入
第一行包含两个整数 $$$N$$$ ($$$1 \leq N \leq 100\,000$$$) 和 $$$M$$$ ($$$0 \leq M \leq 200\,000$$$):分别是节点数和边数。节点由连续整数编号:$$$1、2、\ldots、N$$$。
接下来的 $$$M$$$ 行描述边缘。每行包含三个整数 $$$a$$$、$$$b$$$ 和 $$$c$$$ 表示节点 $$$a$$$ 和 $$$b$$$ ($$$1 \leq a, b \leq N$$$) 之间有一条边,颜色为 $$$c$$$ ($$$1$$$ 表示黑色,$$$2$$$ 表示红色)。
输出
如果有解决方案,第一行应包含单词“YES”,第二行应包含 $$$N$$$ 空格分隔的数字。对于每个 $$$i$$$ ($$$1 \le i \le N$$$),第 $$$i$$$ 个数字应该是分配给节点 $$$i$$$ 的数字。
输出应如下所示:
- 每条边端点处的数字之和与精确值的差异小于$$$10^{-6}$$$;
- 所有指定数字的绝对值之和与最小可能值的差异小于 $$$10^{-6}$$$。
如果有多个有效解,则输出其中任何一个。
如果没有解决方案,则唯一一行应包含单词“NO”。
示例
输入 #1
4 4 1 2 1 2 3 2 1 3 2 3 4 1
输出 #1
YES 0.5 0.5 1.5 -0.5
输入 #2
2 1 1 2 1
输出 #2
YES 0.3 0.7
输入 #3
3 2 1 2 2 2 3 2
输出 #3
YES 0 2 0
输入#4
3 4 1 2 2 2 2 1 2 1 1 1 2 2
输出#4
NO
注意
评分:
子任务:
1.(5分)$$$N \leq 5$$$,$$$M \leq 14$$$
2.(12 点)$$$N \leq 100$$$
3.(17 点)$$$N \leq 1000$$$
4.(24点)$$$N \leq 10\,000$$$
5.(42分)没有进一步的限制
请注意,在第二个示例中,解不是唯一的。