교역 계획

JOI 연방에는 1부터 N까지 번호가 붙은 N개의 도시와, 1부터 M까지 번호가 붙은 M개의 도로가 있다. 도로 i(1 ≤ i ≤ M)는 도시 Ui와 도시 Vi를 양방향으로 연결한다.

JOI 연방은 1부터 K까지 번호가 붙은 K개의 주로 이루어져 있다. 도시 j(1 ≤ j ≤ N)는 주 Sj에 속한다. 또한 어느 주도 도시를 적어도 1개 포함한다.

JOI 연방의 산업 장관인 K 이사장은 앞으로 Q번의 교역을 하고자 한다. k번째 교역(1 ≤ k ≤ Q)은 도시 Ak에서 도시 Bk로 몇 개의 도로와 도시를 지나 특산품을 수송하는 것이다. 다만 이 교역에 협력해 주는 것은 주 SAk와 주 SBk뿐이며(SAk = SBk인 경우에는 주 SAk뿐), 이 주에 속하지 않은 도시를 지나면 특산품을 도둑맞는다.

K 이사장은 특산품을 도둑맞지 않도록 교역할 수 있는 수송 경로가 있는지 알고 싶다. 도시와 도로의 배치, 주와 교역의 정보가 주어졌을 때, 각 교역에서 특산품을 무사히 배달할 수 있는지 판정하는 프로그램을 작성하시오.

입력은 다음 형식으로 표준 입력에서 주어진다.

N M K
U1 V1
U2 V2
:
UM VM
S1 S2 … SN
Q
A1 B1
A2 B2
:
AQ BQ

표준 출력에 Q행으로 출력하시오. k행째(1 ≤ k ≤ Q)에는 k번째 교역에서 특산품을 배달할 수 있으면 1을, 불가능하면 0을 출력하시오.

• 2 ≤ N ≤ 400 000.
• 1 ≤ M ≤ 400 000.
• 1 ≤ K ≤ N.
• 1 ≤ Ui < Vi ≤ N (1 ≤ i ≤ M).
• (Ui, Vi) ≠ (Uj, Vj) (1 ≤ i < j ≤ M).
• 1 ≤ Sj ≤ K (1 ≤ j ≤ N).
• 모든 l(1 ≤ l ≤ K)에 대해 Sj = l인 j(1 ≤ j ≤ N)가 존재한다.
• 1 ≤ Q ≤ 400 000.
• 1 ≤ Ak ≤ N (1 ≤ k ≤ Q).
• 1 ≤ Bk ≤ N (1 ≤ k ≤ Q).
• Ak ≠ Bk (1 ≤ k ≤ Q).
• 입력되는 값은 모두 정수이다.