题目描述

题目译自 BalticOI 2020 Day2 A「Graph」

有一个无向图，它的每条边被染上了红色或黑色。 你的任务是赋予每个节点一个权值，使得：

• 对于每条黑边，其两个端点的权值之和为 $1$
• 对于条红边，其两个端点的权值之和为 $2$
• 所有权值的绝对值之和尽量小

如果没有满足上述要求的解，则返回无解。

输入格式

输入的第一行包括两个整数 $N$ ($1 \leq N \leq 100000$) 和 $M$ ($0 \leq M \leq 200000$) ，分别是节点的个数和边的个数。节点以连续整数 $1,2,\dots,N$ 编号。
接下来的若干行，每行包含三个整数 $a$ , $b$ 和 $c$ ，表示有一条从 $a$ 到 $b$ 的边 ($1 \leq a,b \leq N$) ，其颜色为 $c$ ($1$ 表示黑色，$2$ 表示红色)。

输出格式

如果有解，输出的第一行应该是一个大写英语单词 YES ，第二行应该是用空格隔开的浮点数。对于每个 $i$ ($1\leq i \leq N$)，第 $i$ 个数应该是分配给节点 $i$ 的权值。
输出应保证：

• 每条边的端点权值之和与理论上的端点权值之和之间误差不能超过 $10^{-6}$
• 所有权值的绝对值之和与标准答案之间误差不能超过 $10^{-6}$

如果有多解，输出任意一组解即可。
如果无解，输出应只有一行 NO 。

4 4
1 2 1
2 3 2
1 3 2
3 4 1

YES
0.5 0.5 1.5 -0.5

2 1
1 2 1

YES
0.3 0.7

3 2
1 2 2
2 3 2

YES
0 2 0

3 4
1 2 2
2 2 1
2 1 1
1 2 2

NO

数据范围与提示

对于 $5$ 的测试点， $N \leq 5, M \leq 14$ 。
对于 $12$ 的测试点， $N \leq 100$ 。
对于 $17$ 的测试点， $N \leq 1000$ 。
对于 $24$ 的测试点， $N \leq 10000$ 。
对于 $42$ 的测试点，没有额外约束。

注意，对于第二个样例，答案不唯一。