問題文

$N$ 頂点 $N - 1$ 辺の無向木があります。

各辺には $0$ 以上 $2^{30}$ 未満の整数の重みがついていますが、辺の情報は与えられません。 その代わり、 $M$ 個の、以下の形式の情報が与えられます。

• 頂点 $A_j$ から頂点 $B_j$ への最短パス上の重み全ての XOR は $C_j$ である。

頂点 $X$ から頂点 $Y$ への最短パス上の重み全ての XOR を答えてください。 ただし、与えられた情報が矛盾する場合や、答えが与えられた情報から一意に定まらない場合は、 $-1$ と答えてください。

制約

• $1 \le N, M \le 2 \times 10^5$
• $1 \le X, Y \le N$
• $1 \le A_j, B_j \le N$
• $0 \le C_j \lt 2^{30}$

入力

出力

答えを $1$ 行に出力せよ。

入出力例

5 2 2 5
2 3 2
3 5 3

1

与えられた情報に当てはまるグラフとしては、次のようなものが考えられます。

5 4 1 2
2 5 7
3 5 6
1 4 5
2 3 1

-1

この場合、答えは与えられた情報から一意に定まりません。

7 7 3 6
2 5 10
1 2 6
1 4 20
3 7 1
6 4 48
5 4 24
7 2 3

32