XOR Graph Path Construction

You are given an undirected graph with n vertices and m edges. The i-th edge connects nodes u_i and v_i and has an unknown weight a_i.

For any path in the graph, define its cost as the XOR (denoted by \(\oplus\)) of the weights of the edges along the path. Formally, if a path is given as \( (p_0, p_1, \dots, p_k) \) where each consecutive pair \((p_{i-1},p_i)\) is an edge (and note that vertices and edges may be repeated), and if the corresponding edges in the path are \(e_1, e_2, \dots, e_k\), then the cost of the path is \[ \bigoplus_{i=1}^{k} a_{e_i}. \]

Define \(f(x,y)\) to be the minimum cost among all paths from vertex \(x\) to vertex \(y\). (In particular, \(f(x,x)=0\) for every vertex \(x\)).

You are given the values of \(n\) and \(m\), and for each edge \((u_i,v_i)\) you are given the value of \(f(u_i,v_i)\). Your task is to determine whether there exists a valid assignment of weights \(a_i\) to the edges such that for every edge \((u_i,v_i)\), the minimum cost of all paths from \(u_i\) to \(v_i)\) equals the given value. If a solution exists, you must construct one such assignment.

Hint: One way to solve the problem is to try to assign a potential value \(d[v]\) to every vertex \(v\) so that for every given edge \((u,v)\) with provided value \(w\), the condition \[ d[u] \oplus d[v] = w \] holds. If such an assignment exists, then setting \(a_i = d[u_i] \oplus d[v_i]\) is a valid solution. You need to verify the consistency of these equations over the whole graph.

inputFormat

The first line contains two integers \(n\) and \(m\) (the number of vertices and edges). Each of the following \(m\) lines contains three integers \(u\), \(v\), and \(w\) representing an edge between vertices \(u\) and \(v\) with a given value \(f(u,v)=w\). The vertices are numbered from 1 to \(n\).

Note that the graph is undirected.

outputFormat

If there is no valid assignment of weights \(a_i\) satisfying the conditions, print "NO". Otherwise, print "YES" on the first line. On the second line, print \(m\) integers, where the \(i\)-th integer is the weight \(a_i\) you assign to the \(i\)-th edge (in the same order as the input). If \(m=0\), simply print "YES".

sample

3 3
1 2 1
2 3 2
1 3 3

YES
1 2 3