← 返回题目列表

AtCoder · abc396_e

H. 限制总和的最小值

中文机器翻译题面 查看原题

分数: 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.
例如, 3 \oplus 5 = 6 (二进制: 011 \oplus 101 = 110).

约束

  • 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