题目描述

你有一个无向图，每条边都有一种颜色：红或者黑。

你要做的就是为每个节点配一个实数点权，使得：

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

求一种点权的分配方案。

输入格式

第一行两个整数 $N,M$ 代表点数和边数。
所有点的编号为 $1$ 到 $N$。
接下来 $M$ 行每行三个整数 $a,b,c$ 描述一条边端点为 $a$ 和 $b$，如果 $c$ 是 $1$ 那么这条边是黑色边，如果 $c$ 是 $2$ 那么这条边是红色边。

输出格式

如果有解，首先第一行输出 YES，然后第二行 $N$ 个整数代表可能的一组点权。
多组解输出任意一组即可。
如果无解，一行一个字符串 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

提示

评测方式

您的输出被评判为正确，当且仅当：

• 每条边所连两点的点权和与该边要求的点权间的误差不超过 $10^{-6}$。
• 所有点权的绝对值之和与标准答案误差不超过 $10^{-6}$。

数据规模与约定

本题采用捆绑测试。

• Subtask 1（5 pts）：$N \le 5$，$M \le 14$。
• Subtask 2（12 pts）：$N \le 100$。
• Subtask 3（17 pts）：$N \le 1000$。
• Subtask 4（24 pts）：$N \le 10^4$。
• Subtask 5（42 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le N \le 10^5$，$0 \le M \le 2 \times 10^5$。

本题使用 Special Judge。