Marisa is traveling in the country ABC, which has $n$ cities and $m$ bidirectional roads connecting the cities. The road system ensures that one can travel from any city to any other.
Marisa stays for $q$ days, and each day she starts her tour from city $s$ and ends at city $t$. Marisa takes a photo at the first city, $s$, if $s \leq t$. After that, each time she reaches a city with an index greater than all the indices of the cities she has visited on that day, she takes another photo. She believes a tour is interesting only if she takes a photo at $s$ and one at $t$.
Help her determine for each day whether there exists a route such that her tour is interesting or not. If possible, find the maximum number of photos she can take.
### Input
- The first line contains two positive integers $n$ and $m (1 \le n,m \le 5000)$.
- The next $m$ lines each contain two positive integers $u, v (1 \leq u, v \leq n)$ representing bidirectional roads between cities $u$ and $v$.
- The next line contains a positive integer $q (1 \leq q \leq 2 \times 10^5)$.
- The following $q$ lines each contain two positive integers $s, t (1 \leq s, t \leq n)$.
- Numbers on a line are separated by spaces.
### Output
- Output consists of $q$ lines, where the $i$-th line is an integer indicating the maximum number of photos Marisa can take on the $i$-th day if there exists an interesting route. Otherwise, print `-1`.
### Constraints
- 20% of tests have $n, m \leq 400$.
- 20% of tests have $q \leq 1000, s+1=t$ for all trips.
- 20% of tests have $n \leq 1000, q \leq 1000$.
- 20% of tests have $n \leq 1000$.
- The remaining 20% of tests have no additional constraints.
### Examples
Input:
```
3 2
1 3
3 2
2
1 1
1 2
```
Output:
```
1
-1
```
Input 2:
```
3 3
1 2
2 3
3 1
4
1 2
2 3
3 1
3 3
```
Output 2:
```
2
2
-1
1
```
