심판의 날 프로토콜

프로토콜 '최후의 날'에 따라 살아남은 킹스맨 요원들은 어떤 와인 가게에 도착해야 한다. 요원들은 런던 지하철과 킹스맨의 비밀 터널을 이용할 수 있다. 지하철 노선망은 트리 구조이며, 정점은 역이고 간선은 역 사이의 구간이다. 역은 1부터 $n$까지 번호가 매겨져 있고, 와인 가게는 1번 역에 있다. 모든 구간의 길이는 같다. 요원들은 감시를 받을 수 있고 지하철 이동으로 위치가 드러날 수 있으므로, 지하철은 가게에서 멀어지는 방향으로만 탄다. 즉, 가게에서 첫 번째 역까지의 간선 거리가 가게에서 두 번째 역까지의 거리보다 작을 때에만 인접한 역으로 이동할 수 있다. 각 킹스맨 터널은 두 역을 잇고, 한쪽 역에서 다른 쪽 역으로 가게에서 멀어지는 방향으로만 지하철을 타고 도달할 수 있다.

메를린은 두 번째 프로토콜 발동 시나리오를 검토하고 있다. 각 시나리오는 생존 요원이 처음 있는 역과 사용할 수 있는 킹스맨 터널의 최대 개수로 정해진다. 지하철은 몇 번이든 탈 수 있지만, 가게에서 멀어지는 방향으로만 이동할 수 있다. 메를린은 각 시나리오에서 요원들이 도달할 수 있는 역 중 가게에 가장 가까운 역을 알아야 한다. 남은 길은 요원들이 걸어가야 하기 때문이다.

첫 줄에 역의 개수 $n$이 주어진다 ($2 \le n \le 200\,000$). 다음 $n - 1$개 줄에는 지하철 구간으로 연결된 두 역의 번호 $a_i$, $b_i$가 주어진다 ($1 \le a_i, b_i \le n$).

다음 줄에는 킹스맨 터널의 총개수 $m$이 주어진다 ($0 \le m \le 200\,000$). 다음 $m$개 줄에는 터널로 연결된 두 역의 번호 $u_i$, $v_i$가 주어진다 ($1 \le u_i, v_i \le n$, $u_i \neq v_i$). $v_i$에서 가게에서 멀어지는 방향으로만 이동하여 $u_i$에 도달할 수 있음이 보장된다.

다음 줄에는 시나리오의 개수 $q$가 주어진다 ($0 \le q \le 200\,000$). 다음 $q$개 줄에는 요원들이 처음 있는 역의 번호 $s_i$와 사용할 수 있는 킹스맨 터널의 최대 개수 $k_i$가 주어진다 ($1 \le s_i \le n$, $0 \le k_i \le m$).

각 시나리오에 대해, 요원들이 도달할 수 있는 역 중 가게에 가장 가까운 역의 번호를 한 줄에 하나씩 출력한다.