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\). Đườ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\).

Quốc gia này gồm \(K\) bang, được đánh số từ \(1\) đến \(K\). Thành phố \(j\) (\(1 \le j \le N\)) thuộc bang \(S_j\). Mỗi bang có ít nhất một thành phố.

Chủ tịch K, Bộ trưởng Công nghiệp của Hợp chúng quốc JOI, muốn thực hiện \(Q\) chuyến giao thương. Trong chuyến thứ \(k\) (\(1 \le k \le Q\)), đặc sản được vận chuyển từ thành phố \(A_k\) đến thành phố \(B_k\) qua một số con đường và thành phố. Tuy nhiên, chỉ bang \(S_{A_k}\) và bang \(S_{B_k}\) đồng ý hợp tác; nếu \(S_{A_k}=S_{B_k}\) thì chỉ có bang đó hợp tác. Nếu đi qua một thành phố không thuộc các bang hợp tác, đặc sản sẽ bị đánh cắp.

Chủ tịch K muốn biết có lộ trình nào để thực hiện chuyến giao thương mà không bị đánh cắp đặc sản hay không. Cho thông tin về các thành phố, đường đi, bang và các chuyến giao thương, hãy xác định với từng chuyến liệu có thể vận chuyển đặc sản đến nơi an toàn hay không.

Dữ liệu vào

Dữ liệu vào có dạng:

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

Dữ liệu ra

In ra \(Q\) dòng. Dòng thứ \(k\) (\(1 \le k \le Q\)) chứa \(1\) nếu có thể vận chuyển đặc sản đến nơi an toàn trong chuyến giao thương thứ \(k\), hoặc \(0\) nếu không thể.

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) \ne (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 ít nhất một \(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 \ne B_k\) (\(1 \le k \le Q\)).
• Tất cả các giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. 5 điểm: \(N \le 1000\), \(M \le 1000\), \(Q \le 1000\).
2. 11 điểm: Với mỗi bang \(l\) (\(1 \le l \le K\)), mọi cặp thành phố thuộc bang \(l\) đều có thể đi đến nhau bằng các con đường và chỉ qua 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.

Ví dụ

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

1
0
1

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

0
1
0
1

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

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

Nguồn

Đề bài Trade Plan, JOI 2021/2022, vòng loại thứ hai, bài 5 của Ủy ban Olympic Tin học Nhật Bản. Đề gốc và bản dịch tiếng Việt được cung cấp theo giấy phép CC BY-SA 4.0.