Finding the Ship

The Guardians of the Galaxy received a distress signal from a ship that Thanos destroyed. They must find the ship as soon as possible and rescue Thor, who is on board.

The ship moves in an unusual way. There are $n$ distinct points in the universe, numbered from 1 to $n$, and the ship moves between them. There are also $m$ wormholes, where the $i$-th wormhole connects points $a_i$ and $b_i$. A wormhole may connect a point to itself, and two points may be connected by more than one wormhole. Traveling through any single wormhole takes exactly one hour.

Initially the ship is at point $s$. The Guardians think Thor tried to steer the ship toward one of the points but had to stop along the way. They have $q$ guesses. In the $i$-th guess, Thor started at point $s$ and followed one of the shortest paths to point $v_i$. After passing through wormholes $k_i$ times, the ship stopped and did not move any further. A shortest path is a path that uses the smallest possible number of wormholes.

The first line contains three integers $n$, $m$, and $s$, the number of points, the number of wormholes, and the starting point ($1 \le n, m \le 50000$; $1 \le s \le n$).

Each of the next $m$ lines contains two integers $a_i$ and $b_i$, the points joined by the $i$-th wormhole ($1 \le a_i, b_i \le n$).

The next line contains a single integer $q$, the number of guesses ($1 \le q \le 50000$).

Each of the next $q$ lines contains two integers $v_i$ and $k_i$, the guessed destination and the number of wormholes Thor passed through ($1 \le v_i \le n$; $1 \le k_i \le m$).

For each guess, print one line with one of the following results.

• If the situation in the guess is impossible (for example, there is no path from $s$ to $v_i$), print $0$.
• If the situation is possible and more than one point could hold the ship at that moment, print $-1$.
• Otherwise, print the number of the single point where the ship must be according to the guess.