Shortest Path on a Hexagonal Island

You are given a hexagonal island represented by a set of tiles with given coordinates in the axial coordinate system. Some pairs of tiles are connected by bridges. Your task is to compute the minimum number of bridges you need to cross to travel from a start tile to a destination tile. If it is impossible to reach the destination using the available bridges, output -1.

The island is defined as follows:

• N: The number of tiles.
• tiles: A list of N tiles, each given by its axial coordinates \( (q, r) \).
• B: The number of bridges.
• bridges: A list of B bridges. Each bridge connects two tiles and is given by four integers: \( q_1, r_1, q_2, r_2 \), representing the coordinates of the two tiles connected by that bridge.
• start and destination: Two tiles given by their coordinates \( (q, r) \) where the journey starts and ends, respectively.

The answer is the minimum number of bridges to cross to go from the start tile to the destination tile using a breadth-first search (BFS) algorithm. If the destination cannot be reached via any sequence of bridges, output \( -1 \).

Note: The coordinates are based on the axial coordinate system for hexagonal grids. All formulas should be considered in \( \LaTeX \) format. For example, the coordinate of a tile is given as \( (q, r) \).

inputFormat

The input is read from stdin in the following format:

N
q1 r1
q2 r2
... (N lines total for tile coordinates)
B
q1 r1 q2 r2
q1 r1 q2 r2
... (B lines total for bridges)
start_q start_r
destination_q destination_r

Where:

• N is the number of tiles.
• The next N lines each contain two integers representing the axial coordinates of a tile.
• B is the number of bridges.
• The next B lines each contain four integers representing a bridge between two tiles.
• The next line provides the start tile's coordinates.
• The final line provides the destination tile's coordinates.

outputFormat

Output a single integer to stdout representing the minimum number of bridges that must be crossed to reach the destination from the start. If there is no valid path, output -1.

## sample

6
0 0
1 0
1 -1
0 -1
-1 0
-1 1
7
0 0 1 0
1 0 1 -1
1 -1 0 -1
0 -1 -1 0
-1 0 -1 1
-1 1 0 0
0 0 0 -1
0 0
1 0

1