Background

On January 13, 2024, 15:59:31, as the last submission for interactive Problem J came back with a Wrong Answer, Little G’s EC-Final contest ended, which also meant his first time failing to get a medal in his ICPC career.

After reflecting on it, Little G decided to mass-produce interactive problems for himself to practice. How do you mass-produce interactive problems? As long as there are several unknowns $a_i$ in a data structure, and for each query you give a vector $x$, the interactive library returns a function $f(x)$ related to $a_i$, then you can mass-produce interactive problems!

Then why is this problem not an interactive problem?

Problem Description

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

For any path, define its cost as follows. Let the path be $(p_0, p_1, ..., p_k)$, where $(p_{i-1}, p_i)$ must be an edge in the undirected graph, and suppose it is the $e_i$-th edge. Then the cost of the path is $\bigoplus\limits_{i=1}^{k} a_{e_i}$. Here, $\bigoplus$ denotes XOR. (The path may pass through repeated vertices and repeated edges, i.e., $p$ and $e$ may contain repeated numbers.)

Define $f(x, y)$ as the minimum cost among all paths from $x$ to $y$. In particular, when $x = y$, $f(x, y) = 0$.

Given $n, m$, and for each edge $(u_i, v_i)$ the value $f(u_i, v_i)$, you need to determine whether there exists a valid set of $a_i$. If a solution exists, you also need to construct one.

Input Format

The first line contains two positive integers $n, m$.

Lines $2$ to $m + 1$ each contain two positive integers $u_i, v_i$ and a non-negative integer $f(u_i, v_i)$.

Note: This problem does not guarantee that the graph is connected; there may be multiple edges and self-loops.

Output Format

If no solution exists, output only No.

Otherwise, output Yes on the first line, and output $m$ non-negative integers $a_i$ on the second line representing one valid solution.

There may be many valid answers; in that case, output any one. You must ensure that $0 \le a_i < 2^{63}$.

3 3
1 2 2
2 3 3
3 1 1

Yes
2 3 114514

1 1
1 1 1

No

Hint

Sample Explanation

The graph corresponding to the output answer is as follows:

Consider $f(1, 2)$:

• Consider the path $1 \rightarrow 2$, whose cost is $2$.

• Consider the path $1 \rightarrow 2 \rightarrow 3 \rightarrow 1 \rightarrow 2$, whose cost is $2 \oplus 3 \oplus 114514 \oplus 2 = 114513$.

There are also other paths, but it can be proven that there is no path with cost smaller than $2$, so $f(1, 2) = 2$.

Constraints

This problem uses bundled testdata.

For $100\%$ of the testdata, $1 \le n, m \le 5 \times 10^5$, $1 \le u_i, v_i \le n$, $0 \le f(u_i, v_i) < 2^{31}$.

Translated by ChatGPT 5