문제 설명

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 ... 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
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

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

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

1
1
0
1
0
1
1
1
1
1

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