Capitalism
Contest: Codeforces Global Round 12
Difficulty rating: 2700
Tags: constructive algorithms, dfs and similar, graphs, shortest paths

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.

Input format:
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.

Output format:
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.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
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.

Example input:
6 6
1 2 0
3 2 0
2 5 0
6 5 1
6 3 0
2 4 1

Example output:
YES
3
3 2 1 3 1 0

Example input:
4 4
1 2 1
2 3 0
3 4 1
4 1 1

Example output:
NO

Editorial:
Firstly, each edge connects a person with even income and a person with odd income. So if the graph is not bipartite, then a solution does not exist.
Consider a friendship between people $$$u$$$ and $$$v$$$, where we don't know the direction. Since $$$|a_u-a_v|=1$$$, we know that $$$a_u-a_v\le 1$$$ and $$$a_v-a_u\le 1$$$. Consider a directed friendship $$$(u\to v)$$$. Since $$$a_u+1=a_v$$$, we know that $$$a_v-a_u\le 1$$$ and $$$a_u-a_v\le -1$$$.
For each friendship, let's add two directed edges between them. If it's undirected, we add one from $$$u\to v$$$ of weight $$$1$$$ and one from $$$v\to u$$$ of weight $$$1$$$. If it's directed, we add one from $$$u\to v$$$ of weight $$$1$$$, and one from $$$v\to u$$$ of weight $$$-1$$$.
The way we added these edges ensures that if $$$u$$$ and $$$v$$$ are any two vertices and there is a path of distance $$$d$$$ from $$$u$$$ to $$$v$$$, then $$$a_v-a_u\le d$$$. Note that if a negative cycle exists in our graph, then the inequalities give a contradiction. Otherwise if an answer exists, some vertex $$$u$$$ will have minimum $$$a_u$$$ and another vertex $$$v$$$ will have maximum $$$a_v$$$, and $$$a_v-a_u\le \mathrm{dist}(u\to v)$$$. Therefore, the answer cannot be greater than the diameter: $$$\max_{u,v}\mathrm{dist}(u\to v)$$$. If we find a construction with this answer, then this proves optimality.
Let our construction be as follows. First, choose two vertices $$$u$$$ and $$$v$$$ such that $$$\mathrm{dist}(u\to v)$$$ is maximized. Let's assign $$$a_i=\mathrm{dist}(u\to i)$$$. The property of shortest paths tell us that all the desired inequalities hold for $$$a_i$$$. Then we know all directed friendships are correct: $$$a_v-a_u=1$$$. For all undirected friendships, we know $$$|a_v-a_u|\le 1$$$. Since the graph is bipartite, it cannot hold that $$$a_u=a_v$$$, therefore $$$|a_v-a_u|=1$$$, so all requirements hold and the income inequality is maximized.
For the implementation, we need to check the graph is bipartite, check if negative cycles exist, and find all-pairs shortest paths. For this, we can simply do Floyd-Warshall in $$$O(n^3)$$$ time.