分数: 450 点
问题陈述
给你整数 N, M 和三个长度的整数序列 M: X = (X_1, X_2, \ldots, X_M), Y = (Y_1, Y_2, \ldots, Y_M),和 Z = (Z_1, Z_2, \ldots, Z_M)。保证所有元素 X 和 Y 之间 1 和 N,包括在内。
我们称长度为N 非负整数序列 A = (A_1, A_2, \ldots, A_N) a 好的序列 当且仅当满足以下条件:
- 对于每个整数 i 与 1 \le i \le M,异或 A_{X_i} 和 A_{Y_i} is Z_i.
判断序列是否良好 A=(A_1,A_2,\ldots,A_N) 存在,如果存在,找到一个好的序列,使其元素之和最小化 \displaystyle \sum_{i=1}^N A_i.
异或注意事项
对于非负整数 A 和 B,他们的异或 A \oplus B 定义如下:- 在二进制表示中 A \oplus B,对应位置的数字 2^k \,(k \ge 0) is 1 当且仅当恰好有一个数字位于 A 和 B is 1;否则,就是 0.
约束
- 1 \le N \le 2\times 10^5
- 0 \le M \le 10^5
- 1 \le X_i, Y_i \le N
- 0 \le Z_i \le 10^9
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N M X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_M Y_M Z_M
输出
如果不存在好的序列,则打印 -1.
如果存在一个好的序列,则打印一个好的序列,使其元素之和最小化,并用空格分隔。
如果存在多个具有相同最小和的好序列,则接受打印其中任何一个。
示例输入 1
3 2 1 3 4 1 2 3
示例输出 1
0 3 4
A=(0,3,4) 是一个很好的序列,因为 A_1 \oplus A_2 = 3 和 A_1 \oplus A_3 = 4.
其他好的序列包括 A=(1,2,5) 和 A=(7,4,3),但是 A=(0,3,4) 在所有好的序列中具有最小的总和。
示例输入 2
3 3 1 3 4 1 2 3 2 3 5
示例输出 2
-1
不存在好的序列,因此打印 -1.
示例输入 3
5 8 4 2 4 2 3 11 3 4 15 4 5 6 3 2 11 3 3 0 3 1 9 3 4 15
示例输出 3
0 2 9 6 0