Graph Mex Path Assignment

You are given an undirected graph with n vertices and m edges. The i-th edge connects vertices \(u_i\) and \(v_i\) and is associated with an unknown weight \(a_i\). For any path \((p_0, p_1, \dots, p_k)\) (a path may repeat vertices or edges) where each consecutive pair \((p_{i-1}, p_i)\) is an edge in the graph (say it corresponds to edge \(e_i\)), we define its cost as

[ \mathrm{cost}(\text{path}) = \operatorname{mex}{a_{e_1}, a_{e_2}, \dots, a_{e_k}}, ]

where the \(\operatorname{mex}\) function defined on a multiset of nonnegative integers returns the smallest nonnegative integer which does not appear in the set. In particular, note that for a path consisting of a single edge \((u,v)\) with weight \(a\), the cost is:

[ \operatorname{mex}({a}) = \begin{cases}1, & \text{if } a = 0,\0, & \text{if } a \neq 0.\end{cases} ]

Define \(f(x,y)\) as the minimum cost among all paths from vertex \(x\) to vertex \(y\). By definition, \(f(x,x)=0\) for any vertex \(x\). You are given the integers n and m, and for each edge \((u_i,v_i)\) a value \(f(u_i,v_i)\) is provided. Determine whether there exists a valid assignment of the unknown edge weights \(a_i\) such that for each given edge \((u_i, v_i)\) it holds that f(ui,vi) is exactly the minimum cost over all paths between \(u_i\) and \(v_i)\) under your assignment. If there is a solution, you must output one such assignment.

Observations:

• For an edge \((u,v)\), the direct path (using only this edge) has cost \(\operatorname{mex}(\{a\})\), which is 1 if \(a=0\) and 0 if \(a\neq 0\).
• Thus, for a given edge \((u,v)\) with provided value \(f(u,v)\), if \(f(u,v)=0\) one valid option is to assign \(a\) any positive number (for instance, 1) so that the direct cost is 0.
• If \(f(u,v)=1\), then the only way to have \(\operatorname{mex}(\{a\})=1\) on the direct edge is to assign \(a=0\). However, you must further ensure that every alternative path from \(u\) to \(v)\) contains at least one edge with value 0, because if there is some alternative path that uses only nonzero edges, its cost would be 0, contradicting \(f(u,v)=1\).

A key observation is that since every direct edge yields cost either 0 or 1, any provided value \(f(u,v)\) other than 0 or 1 makes it impossible to satisfy the condition. Hence, we assume that for each provided edge \(f(u,v)\) is either 0 or 1.

Strategy:

• For each edge \((u_i,v_i)\) with \(f(u_i,v_i)=0\), assign \(a_i=1\) (or any positive integer), so that the direct path cost is \(\operatorname{mex}(\{1\}) = 0\).
• For each edge with \(f(u_i,v_i)=1\), assign \(a_i=0\) so that the direct cost is \(\operatorname{mex}(\{0\})=1\).
• However, to ensure the minimum cost truly equals the provided value, for every edge with \(f(u,v)=1\) the alternative paths must not yield cost 0. Notice that an alternative path will yield cost 0 if it uses only edges with nonzero weights. Therefore, if you build a subgraph only consisting of edges with \(f=0\) (which will be assigned a nonzero weight), then for every edge with \(f=1\), its endpoints must not be connected in this subgraph. If they are connected, there exists an alternative path having cost 0, and no valid assignment exists.

Based on the above, the algorithm is:

1. Read \(n\) and \(m\) and the list of edges. Each edge has three numbers: \(u_i, v_i, f_i\) (with \(f_i\) equal to 0 or 1).
2. Construct a union–find (DSU) structure for the subgraph containing only edges with \(f_i=0\).
3. For each edge with \(f_i=1\), if its endpoints are connected in the \(f=0\) subgraph then output NO (no valid assignment exists).
4. If all edges pass the check, output YES and then for each edge in the order of input output the assigned weight:
• If \(f_i=1\), assign \(a_i=0\).
• If \(f_i=0\), assign \(a_i=1\) (or any positive number).

Note: The output format is as follows.

• The first line is either YES or NO.
• If the answer is YES, then the second line should contain \(m\) space-separated integers representing the edge weights \(a_1, a_2, \dots, a_m\) in the order of input.

inputFormat

The first line contains two integers n and m, the number of vertices and the number of edges respectively. The next m lines each contain three integers u_i v_i f_i, where u_i and v_i denote an edge between vertices \(u_i\) and \(v_i\), and f_i is the provided value of \(f(u_i,v_i)\) (which is guaranteed to be either 0 or 1).

outputFormat

If a valid assignment exists, print YES on the first line. On the second line, print \(m\) space-separated integers \(a_1, a_2, \dots, a_m\) representing your assignment of weights to the edges. If no valid assignment exists, print NO.

sample

2 1
1 2 0

YES
1

</p>