Taco BFS Shortest Path Queries

You are given an undirected graph with N intersections and M bidirectional roads. Each road connects two intersections. Your task is to process Q queries, and for each query, determine the shortest path from intersection u to intersection v in terms of the number of intersections visited (including both the start and end intersections).

If a path does not exist between the two intersections, output INF.

The shortest path length d(u,v) can be described in LaTeX as follows:

$$d(u,v)=\min\{k: u=v_0,v_1,\ldots,v_k=v \text{ is a valid path}\}. $$

inputFormat

The input is read from stdin and has the following format:

N M
u1 v1
u2 v2
... (M lines in total)
Q
q1_u q1_v
q2_u q2_v
... (Q lines in total)

Here, the first line contains two integers N (the number of intersections) and M (the number of roads). The next M lines each contain two integers u and v, denoting a road between intersections u and v. This is followed by an integer Q indicating the number of queries, and then Q lines each with two integers representing the start and end intersections for each query.

outputFormat

For each query, output a single line to stdout containing a single integer that represents the number of intersections in the shortest path from the start to the target. If no path exists, output INF.

## sample

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

5
3
3

</p>