Đề bài

Tại Hợp chúng quốc JOI, có $N$ thành phố được đánh số từ $1$ đến $N$, và $M$ con đường được đánh số từ $1$ đến $M$. Con đường $i$ ($1 \le i \le M$) nối hai chiều giữa thành phố $U_i$ và thành phố $V_i$.

Hợp chúng quốc JOI được chia thành $K$ bang được đánh số từ $1$ đến $K$. Thành phố $j$ ($1 \le j \le N$) thuộc bang $S_j$. Ngoài ra, mỗi bang đều có ít nhất $1$ thành phố trực thuộc.

Giám đốc K, Bộ trưởng Công nghiệp của Hợp chúng quốc JOI, dự định thực hiện $Q$ chuyến giao thương từ nay trở đi. Chuyến giao thương thứ $k$ ($1 \le k \le Q$) là vận chuyển đặc sản từ thành phố $A_k$ đến thành phố $B_k$ đi qua một số con đường và thành phố. Tuy nhiên, chỉ có bang $S_{A_k}$ và bang $S_{B_k}$ (hoặc chỉ bang $S_{A_k}$ khi $S_{A_k} = S_{B_k}$) hợp tác trong chuyến giao thương này, và nếu lộ trình đi qua bất kỳ thành phố nào không thuộc các bang này, đặc sản sẽ bị đánh cắp.

Giám đốc K muốn kiểm tra xem có tồn tại lộ trình vận chuyển nào để thực hiện giao thương mà không bị đánh cắp đặc sản hay không. Cho biết cách bố trí các thành phố và con đường, cùng thông tin về các bang và các chuyến giao thương, hãy viết chương trình xác định đối với mỗi chuyến giao thương xem có thể giao đặc sản một cách an toàn hay không.

Ràng buộc

• $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$).
• Với mọi $l$ ($1 \le l \le K$), tồn tại $j$ ($1 \le j \le N$) sao cho $S_j = l$.
• $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$).
• Tất cả các giá trị đầu vào đều là số nguyên.

Subtask

1. ($5$ điểm) $N \le 1\,000$, $M \le 1\,000$, $Q \le 1\,000$.
2. ($11$ điểm) Tất cả các thành phố thuộc bang $l$ ($1 \le l \le K$) có thể đi lại với nhau chỉ bằng cách đi qua các con đường và các thành phố thuộc bang $l$.
3. ($42$ điểm) $N \le 80\,000$, $M \le 80\,000$, $Q \le 80\,000$.
4. ($42$ điểm) Không có ràng buộc bổ sung.

Đầu vào

Đầu vào được cung cấp từ Đầu vào Chuẩn theo định dạng sau:

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

Đầu ra

In ra Đầu ra Chuẩn gồm $Q$ dòng. Trên dòng thứ $k$ ($1 \le k \le Q$), in ra 1 nếu có thể giao đặc sản trong chuyến giao thương thứ $k$, và in ra 0 nếu không thể.

Ví dụ 1

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

1
0
1

• Chuyến giao thương thứ $1$ là vận chuyển đặc sản từ thành phố $1$ đến thành phố $2$ chỉ đi qua các thành phố thuộc bang $1$ hoặc bang $2$. Việc vận chuyển theo thành phố $1$ → thành phố $2$ thỏa mãn điều kiện, nên in ra 1.
• Chuyến giao thương thứ $2$ là vận chuyển đặc sản từ thành phố $1$ đến thành phố $3$ chỉ đi qua các thành phố thuộc bang $1$. Vì không tồn tại lộ trình vận chuyển nào thỏa mãn điều kiện, nên in ra 0.
• Chuyến giao thương thứ $3$ là vận chuyển đặc sản từ thành phố $1$ đến thành phố $4$ chỉ đi qua các thành phố thuộc bang $1$ hoặc bang $2$. Việc vận chuyển theo thành phố $1$ → thành phố $2$ → thành phố $3$ → thành phố $4$ thỏa mãn điều kiện, nên in ra 1.

Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $1, 3, 4$.

Ví dụ 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

Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $1, 3, 4$.

Ví dụ 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

Đầu vào mẫu này thỏa mãn các ràng buộc của tất cả các subtask.

Ví dụ 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

Đầu vào mẫu này thỏa mãn các ràng buộc của Subtask $1, 3, 4$.