cho.sh

交易計画 (Trade Plan)

아직 제출이 없습니다시간 제한4초메모리 제한1024 MB

문제

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

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

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

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 ≦ Ui ＜ Vi ≦ N (1 ≦ i ≦ M)．
  • (Ui, Vi) ≠ (Uj, Vj) (1 ≦ i ＜ j ≦ M)．
  • 1 ≦ Sj ≦ K (1 ≦ j ≦ N)．
  • すべての l (1 ≦ l ≦ K) について，Sj = l となる j (1 ≦ j ≦ N) が存在する．
  • 1 ≦ Q ≦ 400 000．
  • 1 ≦ Ak ≦ N (1 ≦ k ≦ Q)．
  • 1 ≦ Bk ≦ N (1 ≦ k ≦ Q)．
  • Ak ≠ Bk (1 ≦ k ≦ Q)．
  • 入力される値はすべて整数である．