24452번 - 交易計画 (Trade Plan) 서브태스크다국어

JOI 合衆国には 1 から N までの番号が付けられた N 個の都市と，1 から M までの番号が付けられた M 本の道路がある．道路 i (1 ≦ i ≦ M) は，都市 U_i と都市 V_i を双方向に結んでいる．

JOI 合衆国は 1 から K までの番号が付けられた K 個の州からなる．都市 j (1 ≦ j ≦ N) は州 S_j に属している．また，どの州も少なくとも 1 つの都市を含む．

JOI 合衆国の産業大臣である K 理事長は，これから Q 回の交易を行いたいと考えている．k 番目の交易 (1 ≦ k ≦ Q) は，都市 A_k から都市 B_k にいくつかの道路や都市を通って特産品を輸送するというものである．ただし，この交易に協力してくれるのは州 S_Ak と 州 S_Bk のみ (S_Ak = S_Bk の場合は州 S_Ak のみ) であり，これらの州に属していない都市を通ると特産品は盗まれてしまう．

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 ≦ U_i ＜ V_i ≦ N (1 ≦ i ≦ M)．
• (U_i, V_i) ≠ (U_j, V_j) (1 ≦ i ＜ j ≦ M)．
• 1 ≦ S_j ≦ K (1 ≦ j ≦ N)．
• すべての l (1 ≦ l ≦ K) について，S_j = l となる j (1 ≦ j ≦ N) が存在する．
• 1 ≦ Q ≦ 400 000．
• 1 ≦ A_k ≦ N (1 ≦ k ≦ Q)．
• 1 ≦ B_k ≦ N (1 ≦ k ≦ Q)．
• A_k ≠ B_k (1 ≦ k ≦ Q)．
• 入力される値はすべて整数である．