Acquapia

Acquapia는 여러 개의 강이 흐르는 작은 나라이며, 모든 강은 배가 다닐 수 있습니다. 모든 강은 나라 안 산속에서 발원하여 결국 바다로 흘러 들어가고, 어떤 강도 다른 강으로 흘러 들어가지 않습니다. 강은 흐르는 도중(발원지에서는 제외)에 둘 이상의 물줄기로 갈라질 수 있습니다. 강이 시작하거나, 갈라지거나, 끝나는 모든 지점에는 도시가 하나씩 있으며, 각 도시는 많아야 하나의 강에만 접합니다.

강은 Acquapia의 주요 교통수단입니다. 전쟁 중이라 배는 바다를 건널 수 없고 강을 따라서만 이동할 수 있습니다. 두 도시 사이를 이동하려면 배는 물의 흐름을 거슬러 상류로 어떤 도시까지 올라간 뒤, 그 도시에서 물줄기 전환을 하고, 다시 흐름을 따라 하류로 목적지까지 내려갑니다. 물줄기 전환(상류 항해에서 하류 항해로 바꾸는 것)은 어렵고 위험하므로 가능하면 피해야 하며, 반드시 필요할 때에는 경로 위의 정확히 한 도시에서 일어납니다. 오직 상류로만, 또는 오직 하류로만 가는 경우에는 물줄기 전환이 필요 없습니다.

각 강은 발원지를 뿌리로 하고 물이 하류로 흐르는 방향의 트리를 이루므로, 연결된 두 도시 사이의 경로는 유일합니다. 따라서 물줄기 전환이 일어나는 도시도 (존재한다면) 유일하게 결정됩니다.

강, 도시, 그리고 도시 쌍 $X$와 $Y$로 이루어진 질의 목록이 주어질 때, 각 질의에 대해 다음에 답하세요.

• 도시 $X$에서 도시 $Y$로 항해하는 것이 가능한가?
• 가능하다면 물줄기 전환이 필요한가? 필요하다면 어느 도시에서 해야 하는가?

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 공백 하나로 구분된 네 정수 $C$, $R$, $S$, $Q$가 주어집니다. 각각 도시의 수($2 \le C \le 10^3$), 강의 수($1 \le R \le C/2$), 강 구간의 수($1 \le S \le C-1$), 질의의 수($1 \le Q \le 2 \times 10^5$)를 의미합니다. 도시는 $1$번부터 $C$번까지 번호가 매겨집니다.

둘째 줄에는 강의 발원지인 도시들을 나타내는 서로 다른 $R$개의 정수가 주어집니다. 이어지는 $S$개의 줄에는 각각 두 정수 $X$와 $Y$($X \ne Y$)가 주어지며, 도시 $X$에서 하류의 도시 $Y$로 흐르는 강 구간이 있음을 뜻합니다. 그다음 $Q$개의 줄에는 각각 질의를 나타내는 두 정수 $A$와 $B$($A \ne B$)가 주어집니다.

입력의 끝은 $C = R = S = Q = 0$인 줄로 표시되며, 이 줄은 처리하지 않습니다.

각 테스트 케이스에 대해 $Q$개의 줄을 출력합니다. $i$번째 줄에는 입력 순서대로 $i$번째 질의의 답을 출력합니다. 연속한 두 테스트 케이스의 출력 사이에는 빈 줄을 정확히 하나 출력합니다.

각 질의 $(A, B)$에 대해 다음을 출력합니다.

• $A$에서 $B$로 항해할 수 없으면 $-1$;
• 항해할 수 있고 물줄기 전환이 필요 없으면 $0$;
• 그 외의 경우, 물줄기 전환을 해야 하는 도시의 번호.