Delivery Courses

You are given a city with \(N\) intersections and \(M\) bidirectional roads connecting them. Each road connects two intersections. The distance between any two intersections is defined as the number of roads in the shortest path between them. If no path exists between the two intersections, the answer is \(-1\).

You are also given \(Q\) queries. Each query consists of a pair of integers \(s\) and \(t\) representing the start and end intersections for a delivery route.

Your task is to compute the shortest distance (in terms of the number of roads) for each query using a Breadth-First Search (BFS) approach. More formally, for each query, find the minimum number of edges in any path from \(s\) to \(t\); if no such path exists, output \(-1\).

Input constraints: \(1 \leq s, t \leq N\); the roads are given as pairs \(u,v\) with \(1 \leq u,v \leq N\).

inputFormat

The input is given from standard input (stdin) and has the following format:

N M
u1 v1
u2 v2
... (M lines in total)
Q
s1 t1
s2 t2
... (Q lines in total)

Where:

• \(N\) is the number of intersections.
• \(M\) is the number of roads.
• Each of the next \(M\) lines contains two integers \(u\) and \(v\) indicating that there is a road between intersections \(u\) and \(v\).
• \(Q\) is the number of queries.
• Each of the next \(Q\) lines contains two integers \(s\) and \(t\) representing a query.

outputFormat

For each query, output on a new line the shortest number of roads needed to travel from \(s\) to \(t\). If there is no path between \(s\) and \(t\), output \(-1\).

## sample

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

2
2
-1

</p>