Shortest Path Queries in an Undirected Graph

You are given an undirected graph that represents a maze of intersections and bidirectional paths. Each intersection is labeled with an integer from 1 to n. You are also given several queries asking for the shortest path between two intersections.

For each query, determine the minimum number of steps needed to travel from the start intersection to the target intersection. If no such path exists, return -1. The problem can be solved using a breadth-first search (BFS) algorithm.

The graph is provided in a specific format: the first line contains two integers, n and m, followed by m lines each with two integers representing the connected intersections. Then, a number q is given, followed by q lines each containing a pair of integers that form a query.

inputFormat

The first line contains two integers n and m — the number of intersections and the number of paths, respectively.

The next m lines each contain two integers u and v, representing a bidirectional path between intersections u and v.

The following line contains a single integer q — the number of queries.

Each of the next q lines contains two integers a and b, representing a query asking for the shortest path from intersection a to intersection b.

outputFormat

For each query, print the length of the shortest path on a new line. If there is no path between the given intersections, print -1.

## sample

6 7
1 2
2 3
3 4
1 3
3 5
4 5
5 6
4
1 5
2 4
3 6
1 6

2
2
2
3

</p>