社会可以用 $$$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$$$(满足所需的方向)。
在第二个测试中,我们可以证明没有办法分配收入来满足所有要求。