「CMOI R1」图上交互题 / Constructive Minimum Xor Path

2024 年 1 月 13 日 15:59:31，随着最后一发交互 J 题的提交出现了 Wrong Answer，小 G 的 EC-Final 比赛结束了，也意味着在 ICPC 生涯中第一次打铁。 痛定思痛，小 G 决定批量生产交互题给自己做。如何批量生产交互题？只要在一个数据结构中有若干个未知量 $a_i$，每次询问给定向量 $x$，交互库会返回关于 $a_i$ 的函数 $f(x)$，这样就能批量生产交互题了！ ~~那为什么这题并不是交互题呢。~~

给定一个 $n$ 个点，$m$ 条边的**无向图**。第 $i$ 条边 $(u_i,v_i)$ 有一个**未知边权** $a_i$。 对于任何一条**路径**，定义其**代价**如下：设路径为 $(p_0,p_1,...,p_k)$，其中要求 $(p_{i-1},p_i)$ 是无向图中的边，设其为第 $e_i$ 条边。那么路径的代价即为 $\bigoplus\limits_{i=1}^{k} a_{e_i}$。其中 $\bigoplus$ 表示异或。（该路径可以经过重复点和重复边，即 $p$ 和 $e$ 可以包含重复的数） 定义 $f(x,y)$ 为从 $x$ 到 $y$ 的所有路径中代价的**最小值**。特别地，当 $x=y$ 时，$f(x,y)=0$。 给定 $n,m$，再对于每条边 $(u_i,v_i)$ 给定 $f(u_i,v_i)$，你需要求出是否存在一组合法的 $a_i$，如果有解，你还需要构造一组解。

第一行两个正整数 $n,m$。 第 $2\sim m+1$ 行每行两个正整数 $u_i,v_i$ 和一个非负整数 $f(u_i,v_i)$。 **请注意：本题并不保证图连通；可能会存在重边和自环。**

如果不存在解，则仅输出 `No`。 否则，在第一行输出 `Yes`，在第二行输出 $m$ 个非负整数 $a_i$ 表示一组合法的解。 答案可能有很多组，此时输出任意一组解即可。你需要保证 输出的 $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

### 样例解释 答案输出的图如下：  考虑 $f(1,2)$： + 考虑路径 $1\rightarrow 2$，路径的代价为 $2$。 + 考虑路径 $1\rightarrow 2\rightarrow 3\rightarrow 1\rightarrow 2$，路径的代价为 $2\oplus3\oplus114514\oplus2=114513$。 此外还存在其他路径，但可以证明不存在代价比 $2$ 更小的路径，故 $f(1,2)=2$。 ### 数据范围 **本题采用捆绑测试。** |$\text{Subtask}$ |特殊性质|分数| |-:|-:|-:| |$1$|保证有解|$20$| |$2$|$m\le n+10$|$30$| |$3$||$50$| 对于 $100\%$ 的数据，$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}$。