배 찾기

가디언즈 오브 갤럭시는 타노스에게 파괴된 배에서 구조 신호를 받았다. 그들은 가능한 한 빨리 배를 찾아서, 배에 타고 있는 토르를 구해야 한다.

이 배의 이동 방식은 매우 특이하다. 우주에는 1번부터 $n$번까지 번호가 붙은 $n$개의 지점이 있고, 배는 이 지점들 사이를 이동한다. 또 $m$개의 웜홀이 있으며, $i$번째 웜홀은 지점 $a_i$와 $b_i$를 잇는다. 웜홀은 한 지점과 그 자신을 잇을 수도 있고, 두 지점 사이에 웜홀이 둘 이상 있을 수도 있다. 웜홀 하나를 지나는 데는 정확히 1시간이 걸린다.

배는 처음에 지점 $s$에 있었다. 가디언즈는 토르가 배를 어느 지점으로 보내려 했지만 도중에 멈춰야 했다고 짐작한다. 그들에게는 $q$개의 추측이 있다. $i$번째 추측은 다음과 같다. 토르는 지점 $s$에서 출발해 지점 $v_i$로 가는 최단 경로 중 하나를 따라 움직였다. 그러다 웜홀을 정확히 $k_i$번 통과한 뒤 배가 멈추었고, 그 뒤로는 더 움직이지 않았다. 최단 경로는 사용하는 웜홀의 수가 가장 적은 경로이다.

첫 줄에 세 정수 $n$, $m$, $s$가 주어진다. 각각 지점의 수, 웜홀의 수, 출발 지점이다 ($1 \le n, m \le 50000$; $1 \le s \le n$).

이어지는 $m$개의 줄에는 $i$번째 웜홀이 잇는 두 지점 $a_i$와 $b_i$가 주어진다 ($1 \le a_i, b_i \le n$).

다음 줄에는 추측의 수 $q$가 주어진다 ($1 \le q \le 50000$).

이어지는 $q$개의 줄에는 추측된 목적지 $v_i$와 토르가 웜홀을 통과한 횟수 $k_i$가 주어진다 ($1 \le v_i \le n$; $1 \le k_i \le m$).

각 추측에 대해 다음 중 하나의 결과를 한 줄에 출력한다.

• 추측한 상황이 불가능하면 $0$을 출력한다. 예를 들어 지점 $s$에서 $v_i$로 가는 경로가 없는 경우이다.
• 추측한 상황이 가능하고, 그 순간 배가 있을 수 있는 지점이 둘 이상이면 $-1$을 출력한다.
• 그 밖의 경우에는 추측에 따라 배가 반드시 있어야 하는 지점의 번호를 출력한다.