### Problem Statement

There is a directed graph with $N$ vertices and $M$ edges. The vertices are numbered $1$ through $N$, and the $i$-th directed edge goes from vertex $a_i$ to vertex $b_i$.

The cost of a path on this graph is defined as:

-   the maximum index of a vertex on the path (including the initial and final vertices).

Solve the following problem for each $x=1,2,\ldots,Q$.

-   Find the minimum cost of a path from vertex $s_x$ to vertex $t_x$. If there is no such path, print `-1` instead.

The use of fast input and output methods is recommended because of potentially large input and output.

### Input

The input is given from Standard Input in the following format:

```
$N$ $M$
$a_1$ $b_1$
$\vdots$
$a_M$ $b_M$
$Q$
$s_1$ $t_1$
$\vdots$
$s_Q$ $t_Q$
```

### Output

Print $Q$ lines.  
The $i$-th line should contain the answer for $x=i$.

### Constraints

-   $2 \leq N \leq 2000$
-   $0 \leq M \leq N(N-1)$
-   $1 \leq a_i,b_i \leq N$
-   $a_i \neq b_i$
-   If $i \neq j$, then $(a_i,b_i) \neq (a_j,b_j)$.
-   $1 \leq Q \leq 10^4$
-   $1 \leq s_i,t_i \leq N$
-   $s_i \neq t_i$
-   All values in the input are integers.

2
3
-1

For x=1, the path via the 1-st edge from vertex 1 to vertex 2 has a cost of 2, which is the minimum.
For x=2, the path via the 2-nd edge from vertex 2 to vertex 3 and then via the 3-rd edge from vertex 3 to vertex 1 has a cost of 3, which is the minimum.
For x=3, there is no path from vertex 1 to vertex 4, so -1 should be printed.