B - Xor Distances 1.5

2 secs 1024 MB
magurofly

問題文


頂点 辺の無向木があります。

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

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

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

制約


入力


出力


答えを 行に出力せよ。

入出力例


入力例1
5 2 2 5
2 3 2
3 5 3
出力例1
1

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

入力例1

入力例2
5 4 1 2
2 5 7
3 5 6
1 4 5
2 3 1
出力例2
-1

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

入力例3
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
出力例3
32

Submit


Go (1.14)