/ 
実行時間制限: 3 sec / メモリ制限: 1024 MiB
配点 : 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) であって、以下の条件を満たす整数列を 良い整数列 と呼びます。
- 1\le i\le M を満たす全ての整数 i に対し、 A_{X_i} と A_{Y_i} の XOR が Z_i と一致する。
良い整数列 A=(A_1,A_2,\ldots,A_N) が存在するか判定し、存在するならば要素の総和 \displaystyle \sum_{i=1}^N A_i が最小になるような良い整数列を一つ求めてください。
XOR とは
非負整数 A,B の XOR A \oplus B は、以下のように定義されます。- A \oplus B を二進表記した際の 2^k \, (k \geq 0) の位の数は、A,B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 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 と A_2 の XOR が 3 、 A_1 と A_3 の XOR が 4 なので良い整数列です。
この他にも A=(1,2,5),(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
Score : 450 points
Problem Statement
You are given integers N, M and three integer sequences of length M: X = (X_1, X_2, \ldots, X_M), Y = (Y_1, Y_2, \ldots, Y_M), and Z = (Z_1, Z_2, \ldots, Z_M). It is guaranteed that all elements of X and Y are between 1 and N, inclusive.
We call a length-N sequence of non-negative integers A = (A_1, A_2, \ldots, A_N) a good sequence if and only if it satisfies the following condition:
- For every integer i with 1 \le i \le M, the XOR of A_{X_i} and A_{Y_i} is Z_i.
Determine whether a good sequence A=(A_1,A_2,\ldots,A_N) exists, and if it exists, find one good sequence that minimizes the sum of its elements \displaystyle \sum_{i=1}^N A_i.
Notes on XOR
For non-negative integers A and B, their XOR A \oplus B is defined as follows:- In the binary representation of A \oplus B, the digit in the place corresponding to 2^k \,(k \ge 0) is 1 if and only if exactly one of the digits in the same place of A and B is 1; otherwise, it is 0.
Constraints
- 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
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M X_1 Y_1 Z_1 X_2 Y_2 Z_2 \vdots X_M Y_M Z_M
Output
If no good sequence exists, print -1.
If a good sequence exists, print one good sequence that minimizes the sum of its elements, separated by spaces.
If there are multiple good sequences with the same minimum sum, printing any of them is accepted.
Sample Input 1
3 2 1 3 4 1 2 3
Sample Output 1
0 3 4
A=(0,3,4) is a good sequence because A_1 \oplus A_2 = 3 and A_1 \oplus A_3 = 4.
Other good sequences include A=(1,2,5) and A=(7,4,3), but A=(0,3,4) has the smallest sum among all good sequences.
Sample Input 2
3 3 1 3 4 1 2 3 2 3 5
Sample Output 2
-1
No good sequence exists, so print -1.
Sample Input 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
Sample Output 3
0 2 9 6 0