OR is a kind of bitwise operator, we deﬁned that as follow: for two number A and B in binar notation, let C = A OR B. Then for each bit of C, we can get its value by check the digit of corresponding position in A and B. For each digit, 1 OR 1 = 1, 1 OR 0 = 1, 0 OR 1 = 1, 0 OR 0 = 0. And we simply write this operator as |, like 2 | 1 = 3, 2 | 3 = 3.In bitland there is a strange method to calculate the length of a path using OR. If there are M

edges in a path, and the length of them are l1; l2; · · · ; lM, then the length of this path is l1 | l | · · · | lM. Now give you a undirected graph with N nodes and M edges, ﬁnd the OR shortes path between S and T. If S and T are disconnect, we consider the length between them is −1.

## 1005: 【2012四川省热身赛】Problem C. OR Shortest Path

Time Limit: 3 Sec Memory Limit: 128 MBSubmit: 1 Solved: 0

[Submit][Status][Web Board]

## Description

## Input

First line of the input is a single integer T(T ≤ 30), indicates there are T test cases.

For each test case, the ﬁrst line is four integers N(2 ≤ N ≤ 10^{4}), M(1 ≤ M ≤ 10^{5}), S,T(1 ≤ S; T ≤ N; S ̸= T), indicates the number of nodes, the number of egdes, the startingnode and the target node respectively. Following M lines, each line contains three integers a bc(1 ≤ a; b ≤ N, a ̸= b, 0 ≤ c < 2^{30}), means there exist an undirected edge between node a and node b, and the length is c.

## Output

For each test case, output one line. First ,output “Case #t: ”, where t is the number of test case,

from 1 to T. Then, you should output a single line contains a single number means the length of

the OR shortest path between S and T or −1.

## Sample Input

```
3
4 4 1 4
1 2 1
1 3 2
2 4 2
3 4 1
4 4 1 4
1 2 6
1 3 2
2 4 2
3 4 5
4 2 1 4
1 2 4
3 4 5
```

## Sample Output

```
Case #1: 3
Case #2: 6
Case #3: -1
```