## Mock CCC '20 Contest 1 S3 - Tree Programming

View as PDF

Points: 10 (partial)
Time limit: 7.0s
Memory limit: 512M

Author:
Problem type

A tree is a strange type of graph. We will not be dealing with trees today, as they are too hard.

You are instead given a graph of nodes and edges. Edge connects nodes and with a value of . A path from to consists of a sequence of the edges, such that consecutive edges in the path share a common node. The value of this path is the bitwise OR of all the edge values in the path.

Given queries, , can you determine the minimum path value of a path from to ?

#### Input Specification

The first line will contain three integers .

The next lines will each contain three integers, , indicating there is an edge between nodes and of value . Note that there may be duplicate edges between nodes. It is guaranteed that the entire graph is connected.

The next lines will each contain two integers, .

#### Output Specification

For each query, output one integer, the minimum path value.

For 2/15 of the points,

For an additional 3/15 of the points,

#### Sample Input 1

3 4 2
1 2 1
2 3 1
1 3 0
2 3 0
1 3
1 2

#### Sample Output 1

0
0

Note: You do not need to pass sample 2 for subtask 1 or 2.

#### Sample Input 2

4 5 5
1 3 3
1 2 2
2 3 1
3 4 4
2 4 1
1 3
1 4
3 4
2 3
1 2

#### Sample Output 2

3
3
1
1
2