교역 계획

문제

JOI 합중국에는 $1$ 부터 $N$ 까지의 번호가 붙은 $N$ 개의 도시와, $1$ 부터 $M$ 까지의 번호가 붙은 $M$ 개의 도로가 있다. 도로 $i$ ($1 \le i \le M$) 는 도시 $U_{i}$ 와 도시 $V_{i}$ 를 양방향으로 연결한다.

JOI 합중국은 $1$ 부터 $K$ 까지의 번호가 붙은 $K$ 개의 주로 이루어져 있다. 도시 $j$ ($1 \le j \le N$) 는 주 $S_{j}$ 에 속해 있다. 또한, 어느 주도 적어도 $1$ 개의 도시를 포함한다.

JOI 합중국의 산업부 장관인 K 이사장은, 이제부터 $Q$ 번의 교역을 하려고 한다. $k$ 번째 교역 ($1 \le k \le Q$) 은, 도시 $A_{k}$ 에서 도시 $B_{k}$ 로 몇 개의 도로와 도시를 거쳐 특산품을 수송하는 것이다. 다만, 이 교역에 협력해 주는 것은 주 $S_{A_{k}}$ 와 주 $S_{B_{k}}$ 뿐이며 ($S_{A_{k}} = S_{B_{k}}$ 인 경우에는 주 $S_{A_{k}}$ 뿐이다), 이 주들에 속하지 않은 도시를 지나면 특산품은 도난당하고 만다.

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

제한

• $2 \le N \le 400\,000$.
• $1 \le M \le 400\,000$.
• $1 \le K \le N$.
• $1 \le U_{i} < V_{i} \le N$ ($1 \le i \le M$).
• $(U_{i}, V_{i}) \neq (U_{j}, V_{j})$ ($1 \le i < j \le M$).
• $1 \le S_{j} \le K$ ($1 \le j \le N$).
• 모든 $l$ ($1 \le l \le K$) 에 대해, $S_{j} = l$ 이 되는 $j$ ($1 \le j \le N)$ 가 존재한다.
• $1 \le Q \le 400\,000$.
• $1 \le A_{k} \le N$ ($1 \le k \le Q$).
• $1 \le B_{k} \le N$ ($1 \le k \le Q$).
• $A_{k} \neq B_{k}$ ($1 \le k \le Q$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($5$ 점) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ 점) 주 $l$ ($1 \le l \le K$) 에 속하는 모든 도시는, 도로와 주 $l$ 에 속하는 도시만을 지나서 서로 오갈 수 있다.
3. ($42$ 점) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 표준 입력에서 주어진다.
$N$ $M$ $K$
$U_{1}$ $V_{1}$
$U_{2}$ $V_{2}$
$:$
$U_{M}$ $V_{M}$
$S_{1}$ $S_{2}$ $\dots$ $S_{N}$
$Q$
$A_{1}$ $B_{1}$
$A_{2}$ $B_{2}$
$:$
$A_{Q}$ $B_{Q}$

출력

표준 출력에 $Q$ 줄로 출력한다. $k$ 번째 줄 ($1 \le k \le Q$) 에는, $k$ 번째 교역에서 특산품을 배달하는 것이 가능하면 1 을, 불가능하면 0 을 출력한다.

채점 관련 주의사항

모든 제출은 채점 시스템에서 채점된다.

제출된 소스 코드는, 서브태스크에 대응하는 모든 채점용 입력 데이터에 대해 올바른 결과를 반환했을 때, 그 서브태스크에 대해 정답으로 인정된다.

각 제출의 점수는, 제출된 소스 코드에 대해 정답으로 인정된 서브태스크의 점수의 합이다.

이 과제의 점수는, 이 과제에 대한 모든 제출의 점수의 최댓값이다.

현재 점수는 「제출 결과」 탭의 「나의 점수 현황」에서 확인할 수 있다.

예제 입력 1

4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4

예제 출력 1

1
0
1

• $1$ 번째 교역은, 주 $1$ 또는 주 $2$ 에 속하는 도시만을 지나서, 도시 $1$ 에서 도시 $2$ 로 특산품을 수송하는 것이다. 도시 $1$ → 도시 $2$ 로 수송하면 조건을 만족하므로, 1 을 출력한다.
• $2$ 번째 교역은, 주 $1$ 에 속하는 도시만을 지나서, 도시 $1$ 에서 도시 $3$ 으로 특산품을 수송하는 것이다. 조건을 만족하는 수송 경로는 존재하지 않으므로, 0 을 출력한다.
• $3$ 번째 교역은, 주 $1$ 또는 주 $2$ 에 속하는 도시만을 지나서, 도시 $1$ 에서 도시 $4$ 로 특산품을 수송하는 것이다. 도시 $1$ → 도시 $2$ → 도시 $3$ → 도시 $4$ 로 수송하면 조건을 만족하므로, 1 을 출력한다.

이 예제는 서브태스크 $1, 3, 4$ 의 제약을 만족한다.

예제 입력 2

4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4

예제 출력 2

0
1
0
1

이 예제는 서브태스크 $1, 3, 4$ 의 제약을 만족한다.

예제 입력 3

6 5 3
1 2
3 4
5 6
1 4
3 5
1 1 2 2 3 3
4
1 4
1 5
3 6
4 3

예제 출력 3

1
0
1
1

이 예제는 모든 서브태스크의 제약을 만족한다.

예제 입력 4

8 11 3
4 8
1 8
4 6
3 5
2 4
7 8
6 7
3 4
1 4
2 3
3 8
2 3 1 1 2 1 2 1
10
8 2
8 1
2 7
5 3
5 7
4 8
1 8
6 8
6 5
1 8

예제 출력 4

1
1
0
1
0
1
1
1
1
1

이 예제는 서브태스크 $1, 3, 4$ 의 제약을 만족한다.