AT_abc396_e [ABC396E] Min of Restricted Sum

整数 $ 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 $ である。 例えば、 $ 3 \oplus 5 = 6 $ となります (二進表記すると： $ 011 \oplus 101=110 $ )。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ X_1 $ $ Y_1 $ $ Z_1 $ $ X_2 $ $ Y_2 $ $ Z_2 $ $ \vdots $ $ X_M $ $ Y_M $ $ Z_M $

良い整数列が存在しないならば $ -1 $ を出力せよ。 良い整数列が存在するならば要素の総和が最小になる良い整数列を一つ空白区切りで出力せよ。 なお、要素の総和が最小となる良い整数列が複数存在する場合は、どれを出力しても正答となる。

### Sample Explanation 1 $ 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) $ です。 ### Sample Explanation 2 良い整数列は存在しないので、 $ -1 $ を出力してください。 ### 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 $ - 入力される値は全て整数