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≤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≤n,m≤5000).
- The next m lines each contain two positive integers u,v(1≤u,v≤n) representing bidirectional roads between cities u and v.
- The next line contains a positive integer q(1≤q≤2×105).
- The following q lines each contain two positive integers s,t(1≤s,t≤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≤400.
- 20% of tests have q≤1000,s+1=t for all trips.
- 20% of tests have n≤1000,q≤1000.
- 20% of tests have n≤1000.
- The remaining 20% of tests have no additional constraints.
### Examples
Input:
32133221112
Output:
1-1
Input 2:
33122331412233133
Output 2:
22-11
