C. Tourist
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

The Construction Kingdom is a famous tourist attraction, attracting thousands of tourists every year. The kingdom consists of $$$n$$$ towns and $$$m$$$ directed roads. Each road has a length of $$$1$$$. It is guaranteed that among the initial $$$m$$$ roads, there are no duplicate roads and no road from a town to itself.

Later, due to the continuous prosperity of tourism, the Construction Kingdom decided to expand the roads. Starting from day $$$1$$$, over the next $$$k$$$ days, a new directed road from $$$x$$$ to $$$y$$$ will be built each day. Due to improper planning, it may happen that an already existing road is built, or a road from a town to itself is built.

Fengmi is a free-spirited tourist. She has $$$q$$$ travel wishes and a desired distance $$$w$$$. Each wish has a start $$$s$$$ and an end $$$t$$$ ($$$s_i$$$ and $$$t_i$$$ may be the same). She wants to know, for each wish, the earliest day on which she can start from town $$$s$$$, and under the condition that she is allowed to pass through towns and roads multiple times, exactly travel a distance of $$$w$$$ to reach town $$$t$$$, or report that it is impossible. Please help her solve this problem.

Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 200$$$, $$$1 \le m \le n(n-1)$$$) — the number of towns and the number of initial roads.

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$), indicating a directed road from $$$u_i$$$ to $$$v_i$$$.

The next line contains an integer $$$k$$$ ($$$1 \le k \le n^2$$$) — the number of roads to be built in the following days.

Each of the next $$$k$$$ lines contains two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), meaning that on day $$$i$$$, a new directed road from $$$x_i$$$ to $$$y_i$$$ is built.

The next line contains two integers $$$q$$$ and $$$w$$$ ($$$1 \le q \le n^2$$$, $$$1 \le w \le 10^9$$$) — the number of wishes and the desired distance.

Each of the next $$$q$$$ lines contains two integers $$$s_i$$$ and $$$t_i$$$ ($$$1 \le s_i, t_i \le n$$$) — the start and end of the $$$i$$$-th wish.

Output

For each wish, output a single integer — the earliest day that the wish can be fulfilled (i.e., after the road built on that day, there exists a walk of length exactly $$$w$$$ from $$$s$$$ to $$$t$$$). If it is never possible, output $$$-1$$$.

Example
Input
6 3
1 3
2 3
3 1
4
4 5
5 5
2 5
5 6
5 8
5 1
5 5
1 1
4 5
4 6
Output
-1
2
0
2
4
Note

In the sample, the desired distance is $$$w = 8$$$.

  • For the first wish, it can be proved that it is impossible.
  • For the second wish, after the roads $$$4 \to 5$$$ and $$$5 \to 5$$$ are built, one can walk along the town sequence $$$[5, 5, 5, 5, 5, 5, 5, 5, 5]$$$ to reach the destination.
  • For the third wish, initially one can walk along the town sequence $$$[1, 3, 1, 3, 1, 3, 1, 3, 1]$$$ to the destination.
  • For the fourth wish, after the roads $$$4 \to 5$$$, $$$5 \to 5$$$ are built, one can walk along the town sequence $$$[4, 5, 5, 5, 5, 5, 5, 5, 5]$$$ to the destination.
  • For the fifth wish, after the roads $$$4 \to 5$$$, $$$5 \to 5$$$, $$$2 \to 5$$$, $$$5 \to 6$$$ are built, one can walk along the town sequence $$$[4, 5, 5, 5, 5, 5, 5, 5, 6]$$$ to the destination.