CF1450E Capitalism

整个社会可以用一张由 $n$ 个顶点和 $m$ 条边组成的无向联通图来表示。顶点代表人，一条边 $(i,j)$ 代表人 $i$ 和 $j$ 之间的友谊。 在社会上，第 $i$ 个人有收入 $a_i$。一个人 $i$ 羡慕一个人 $j$，等价于 $j$ 比 $i$ 多出1个单位的收入，也就是 $a_j=a_i+1$。 如果对于每一对朋友，都有一个人羡慕另一个人，这个社会就叫物欲社会。对于一些朋友关系，你知道哪个人在羡慕另一个人。对于其余的朋友关系，你不知道谁羡慕谁。 社会收入不等值的定义是：$\max_{i=1}^na_i - \min_{i=1}^na_i$，也就是社会中收入最多的人的收入与收入最少的人的收入之差。 你只知道一些朋友关系，不知道每个人的收入。对于一部分朋友关系，你知道谁羡慕谁；对于另外一部分，你不知道。你要判断这个社会是否可能成为物欲社会。如果是，你要构造一个 $a$ 满足所有条件，且这是个物欲社会。要求你给出的 $a$ 让社会收入不等值最大。

第一行两个整数 $n$，$m$，分别表示人数和条件数。$n \le 200, n-1 \le m \le 2000$。 接下来 $m$ 行，每行三个整数 $i$，$j$，$b$，表示一个关系。如果 $b=1$，那么 $a_j=a_i+1$；如果 $b=0$，那么 $|a_i-a_j|=1$。 保证 $b=0/1,1\le i,j \le n$，且不会有重复的 $(i,j)$。

第一行一个字符串 $\texttt{YES}$ 或者 $\texttt{NO}$。大小写随意。表示这个社会是否可以是物欲社会。 如果有解，在第二行输出一个最大社会收入不等值，在第三行输出 $n$ 个整数表示每个人的收入。 保证如果有解，存在一组解，让每个人的收入都不超过 $10^6$。

In the first test, we can show that an income inequality greater than $ 3 $ is impossible for the given society. In the given answer with income inequality equal to $ 3 $ : - Person $ 2 $ is envious of person $ 1 $ . - Person $ 3 $ is envious of person $ 2 $ . - Person $ 5 $ is envious of person $ 2 $ . - Person $ 6 $ is envious of person $ 5 $ (the required direction is satisfied). - Person $ 6 $ is envious of person $ 3 $ . - Person $ 2 $ is envious of person $ 4 $ (the required direction is satisfied). In the second test, we can show that there is no way to assign incomes to satisfy all requirements.