P11170 "CMOI R1" Interactive Problem on Graph / Constructive Minimum Xor Path

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?~~

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.

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.**

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}$.

### 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.** |$\text{Subtask}$|Special Property|Score| |-:|-:|-:| |$1$|A solution is guaranteed to exist.|$20$| |$2$|$m \le n + 10$|$30$| |$3$||$50$| 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