CF1450E.Capitalism

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.

一个社会可以由一个包含 $n$ 个顶点和 $m$ 条边的连通无向图表示。其中，顶点代表人，边 $(i,j)$ 表示人 $i$ 与人 $j$ 之间的友谊关系。

在该社会中，第 $i$ 个人的收入为 $a_i$。若 $a_j = a_i + 1$，则称人 $i$ 嫉妒人 $j$；即，当人 $j$ 的收入恰好比人 $i$ 高 $1$ 单位时，人 $i$ 嫉妒人 $j$。

若对每一对朋友，其中一人都嫉妒另一人，则该社会被称为资本主义社会。对于某些友谊关系，你已知哪一方嫉妒另一方；而对于其余的友谊关系，你并不知道嫉妒的方向。

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

你仅知道友谊关系（即图的结构），而不知道任何人的具体收入。若根据已有信息，该社会不可能成为资本主义社会，则应报告这一情况；否则，请找出一组收入分配方案，使得该社会是资本主义社会，并且收入不平等度尽可能大。

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.

第一行包含两个整数 $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$，则要求其中一人嫉妒另一人，方向不限。

任意两人之间至多存在一条友谊关系。保证若将所有友谊视为无向边，则所构成的图是连通的。

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.

如果该社会有可能是资本主义社会，则输出 “YES”，否则输出 “NO”。你可以以任意大小写形式输出字符（大写或小写）。

如果答案为 “YES”，则还需额外输出两行：第一行输出可能的最大收入不平等程度；第二行输出 $n$ 个整数 $a_1,\ldots, a_n$（满足 $0\le a_i\le 10^6$），其中 $a_i$ 表示第 $i$ 个人的收入。

我们可以证明：若存在解，则必存在一个解使得对所有 $i$ 均满足 $0\le a_i\le 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.

在第一个测试中，我们可以证明：对于给定的社会，收入不平等程度大于 $3$ 是不可能的。在给出的、收入不平等程度恰好为 $3$ 的答案中：

• 人物 $2$ 嫉妒人物 $1$；
• 人物 $3$ 嫉妒人物 $2$；
• 人物 $5$ 嫉妒人物 $2$；
• 人物 $6$ 嫉妒人物 $5$（满足所要求的方向）；
• 人物 $6$ 嫉妒人物 $3$；
• 人物 $2$ 嫉妒人物 $4$（满足所要求的方向）。

在第二个测试中，我们可以证明：不存在一种收入分配方式能满足所有约束条件。