P17890 [ICPC 2026 Nanchang I] Tourist

Description

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 Format

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 Format

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$.

Explanation/Hint

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.