← 返回题目列表

Codeforces · 1450/E

E. 资本主义

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

社会可以用 $$$n$$$ 个顶点和 $$$m$$$ 个边的连通无向图来表示。顶点代表人,边 $$$(i,j)$$$ 代表人 $$$i$$$ 和 $$$j$$$ 之间的友谊。

在社会中,第 $$$i$$$ 人的收入为 $$$a_i$$$。如果$$$a_j=a_i+1$$$,则$$$i$$$ 嫉妒人$$$j$$$。也就是说,如果$$$j$$$ 的收入单位比$$$i$$$ 多$$$1$$$。

如果每对朋友都互相嫉妒,那么这个社会就被称为资本主义社会。对于某些友谊,你知道哪个朋友羡慕另一个朋友。剩下的友情,你不知道羡慕的方向。

社会收入不平等定义为 $$$\max\limits_{1 \leq i \leq n} a_i - \min\limits_{1 \leq i \leq n} a_i$$$。

你只知道友谊,不知道收入。如果以现有的知识,这个社会不可能成为资本主义,那么你应该报告这一点。否则,你应该找到一种收入分配,其中社会是资本主义的,并且收入不平等最大化。

输入

第一行包含两个整数 $$$n$$$, $$$m$$$ ($$$1\le n\le 200$$$, $$$n-1\le m\le 2000$$$) — 分别是人数和友谊数。

以下 $$$m$$$ 行描述了友谊。每个友谊由三个整数 $$$i$$$、$$$j$$$、$$$b$$$ ($$$1\le i, j\le n, i\ne j, 0\le b\le 1$$$) 描述。这表示$$$i$$$ 和$$$j$$$ 是朋友。如果$$$b=1$$$,我们要求$$$i$$$ 嫉妒人$$$j$$$。如果$$$b=0$$$,一个朋友应该在任一方向羡慕另一个朋友。

每对人之间至多有一段友谊。如果我们将友谊视为无向边,则可以保证该图是连通的。

输出

如果社会可能是资本主义,则打印“是”,否则打印“否”。您可以以任何大小写(大写或小写)打印字符。

如果答案是“是”,您应该额外打印两行。在第一行中,打印最大可能的收入不平等。在下一行中,您应该打印 $$$n$$$ 整数 $$$a_1,\ldots, a_n$$$ ($$$0\le a_i\le 10^6$$$),其中 $$$a_i$$$ 表示第 $$$i$$$ 人的收入。

我们可以证明,如果存在解,则对于所有$$$i$$$,存在$$$0\le a_i\le 10^6$$$ 的解。

如果存在多个解,则打印任意一个。

示例

输入 #1

6 6
1 2 0
3 2 0
2 5 0
6 5 1
6 3 0
2 4 1

输出 #1

YES
3
3 2 1 3 1 0

输入 #2

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

输出 #2

NO

输入 #3

1 0

输出 #3

YES
0
0

注意

在第一个测试中,我们可以证明,对于给定的社会,收入不平等大于 $$$3$$$ 是不可能的。在给出的答案中,收入不平等等于 $$$3$$$:

- 人 $$$2$$$ 嫉妒人 $$$1$$$。
- 人 $$$3$$$ 嫉妒人 $$$2$$$。
- 人 $$$5$$$ 嫉妒人 $$$2$$$。
- 人 $$$6$$$ 嫉妒人 $$$5$$$(满足所需的方向)。
- 人 $$$6$$$ 嫉妒人 $$$3$$$。
- 人 $$$2$$$ 嫉妒人 $$$4$$$(满足所需的方向)。

在第二个测试中,我们可以证明没有办法分配收入来满足所有要求。