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$。

题目描述

A society can be represented by a connected, undirected graph of $ n $ vertices and $ m $ edges. The vertices represent people, and an edge $ (i,j) $ represents a friendship between people $ i $ and $ j $ . In society, the $ i $ -th person has an income $ a_i $ . A person $ i $ is envious of person $ j $ if $ a_j=a_i+1 $ . That is if person $ j $ has exactly $ 1 $ more unit of income than person $ i $ . The society is called capitalist if for every pair of friends one is envious of the other. For some friendships, you know which friend is envious of the other. For the remaining friendships, you do not know the direction of envy. The income inequality of society is defined as $ \max\limits_{1 \leq i \leq n} a_i - \min\limits_{1 \leq i \leq n} a_i $ . You only know the friendships and not the incomes. If it is impossible for this society to be capitalist with the given knowledge, you should report about it. Otherwise, you should find an assignment of incomes in which the society is capitalist, and the income inequality is maximized.

输入输出格式

输入格式

The first line contains two integers $ n $ , $ m $ ( $ 1\le n\le 200 $ , $ n-1\le m\le 2000 $ ) — the number of people and friendships, respectively. The following $ m $ lines describe the friendships. Each friendship is described by three integers $ i $ , $ j $ , $ b $ ( $ 1\le i, j\le n, i\ne j, 0\le b\le 1 $ ). This denotes that people $ i $ and $ j $ are friends. If $ b=1 $ , we require that person $ i $ is envious of person $ j $ . If $ b=0 $ , one friend should be envious of the other in either direction. There is at most one friendship between each pair of people. It is guaranteed that if we consider the friendships as undirected edges, the graph is connected.

输出格式

Print "YES" if it is possible that the society is capitalist, or "NO" otherwise. You can print characters in any case (upper or lower). If the answer is "YES", you should print two additional lines. In the first line, print the maximum possible income inequality. On the next line you should print $ n $ integers $ a_1,\ldots, a_n $ ( $ 0\le a_i\le 10^6 $ ), where $ a_i $ denotes the income of the $ i $ -th person. We can prove that if there exists a solution, there exists one where $ 0\le a_i\le 10^6 $ for all $ i $ . If there exist multiple solutions, print any.

输入输出样例

输入样例 #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

说明

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.