/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 400 点
問題文
頂点に 1 から N の、辺に 1 から M の番号がついたN 頂点 M 辺の有向グラフがあります。辺 i は頂点 A_i から頂点 B_i への重み W_i の有向辺です。
頂点 1 から頂点 N への walk のうち、walk に含まれる辺の重みのビット単位 \mathrm{XOR} の最小値を求めてください。
頂点 1 から頂点 N への walk とは
直感的には、「頂点 1 から頂点 N への経路であって、同じ頂点や同じ辺を複数回通っても良いもの」です。 正確には、辺の列 (e_1,\ldots,e_k) であって、以下の条件を全て満たすものです。
- e_1 は頂点 1 を始点とする。
- 全ての 1 \leq i < k について、e_i の終点と e_{i+1} の始点は一致する。
- e_k は頂点 N を終点とする。
ビット単位 \mathrm{XOR} 演算とは
非負整数 A, B のビット単位 \mathrm{XOR} 、A\ \mathrm{XOR}\ B は、以下のように定義されます。
- A\ \mathrm{XOR}\ B を二進表記した際の 2^k (k \geq 0) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 0 である。
一般に k 個の非負整数 p_1, p_2, p_3, \dots, p_k のビット単位 \mathrm{XOR} は (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k) と定義され、これは p_1, p_2, p_3, \dots p_k の順番によらないことが証明できます。
制約
- 2 \leq N \leq 1000
- 0 \leq M \leq 1000
- 1 \leq A_i,B_i \leq N
- 0 \leq W_i < 2^{10}
- 入力は全て整数
入力
入力は以下の形式で標準入力から与えられる。
N M A_1 B_1 W_1 A_2 B_2 W_2 \vdots A_M B_M W_M
出力
頂点 1 から頂点 N への walk が存在しない場合、-1 と出力せよ。
頂点 1 から頂点 N への walk が存在する場合、そのうち、walk に含まれる辺の重みのビット単位 \mathrm{XOR} の最小値を出力せよ。
入力例 1
3 3 1 2 4 2 3 5 1 3 2
出力例 1
1
(辺 1, 辺 2) という walk に含まれる辺の重みのビット単位 \mathrm{XOR} は 1 となります。
入力例 2
4 4 1 4 7 4 2 2 2 3 4 3 4 1
出力例 2
0
(辺 1, 辺 2, 辺 3, 辺 4) という walk に含まれる辺の重みのビット単位 \mathrm{XOR} は 0 となります。
途中に頂点 N を含んでも良いことに注意してください。
入力例 3
999 4 1 2 9 2 1 8 1 2 7 1 1 6
出力例 3
-1
頂点 1 から頂点 N への walk が存在しない場合、-1 と出力してください。
Score : 400 points
Problem Statement
There is a directed graph with N vertices and M edges, where vertices are numbered from 1 to N and edges are numbered from 1 to M. Edge i is a directed edge from vertex A_i to vertex B_i with weight W_i.
Find the minimum value of the bitwise \mathrm{XOR} of the weights of edges included in a walk from vertex 1 to vertex N.
What is a walk from vertex 1 to vertex N?
Intuitively, it is "a path from vertex 1 to vertex N that may visit the same vertex or edge multiple times." Formally, it is a sequence of edges (e_1,\ldots,e_k) that satisfies all of the following conditions:
- e_1 starts at vertex 1.
- For all 1 \leq i < k, the endpoint of e_i and the starting point of e_{i+1} are the same.
- e_k ends at vertex N.
What is the bitwise \mathrm{XOR} operation?
The bitwise \mathrm{XOR} of non-negative integers A and B, denoted A\ \mathrm{XOR}\ B, is defined as follows:
- When A\ \mathrm{XOR}\ B is written in binary, the digit at the 2^k place (k \geq 0) is 1 if exactly one of the digits at the 2^k place of A and B in binary is 1, and 0 otherwise.
In general, the bitwise \mathrm{XOR} of k non-negative integers p_1, p_2, p_3, \dots, p_k is defined as (\dots ((p_1\ \mathrm{XOR}\ p_2)\ \mathrm{XOR}\ p_3)\ \mathrm{XOR}\ \dots\ \mathrm{XOR}\ p_k), and it can be proved that this does not depend on the order of p_1, p_2, p_3, \dots p_k.
Constraints
- 2 \leq N \leq 1000
- 0 \leq M \leq 1000
- 1 \leq A_i,B_i \leq N
- 0 \leq W_i < 2^{10}
- All input values are integers.
Input
The input is given from Standard Input in the following format:
N M A_1 B_1 W_1 A_2 B_2 W_2 \vdots A_M B_M W_M
Output
If there is no walk from vertex 1 to vertex N, output -1.
If there is a walk from vertex 1 to vertex N, output the minimum value of the bitwise \mathrm{XOR} of the weights of edges included in such a walk.
Sample Input 1
3 3 1 2 4 2 3 5 1 3 2
Sample Output 1
1
The bitwise \mathrm{XOR} of the weights of edges included in the walk (edge 1, edge 2) is 1.
Sample Input 2
4 4 1 4 7 4 2 2 2 3 4 3 4 1
Sample Output 2
0
The bitwise \mathrm{XOR} of the weights of edges included in the walk (edge 1, edge 2, edge 3, edge 4) is 0.
Note that the walk may include vertex N in the middle.
Sample Input 3
999 4 1 2 9 2 1 8 1 2 7 1 1 6
Sample Output 3
-1
If there is no walk from vertex 1 to vertex N, output -1.