交易計画 (Trade Plan)

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

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

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

K 理事長は特産品が盗まれないように交易を行うような輸送経路があるのかを調べたい．都市と道路の配置，州と交易の情報が与えられたとき，各交易について特産品を無事届けることが可能かを判定するプログラムを作成せよ．

• \(2 \leqq N \leqq 400\,000\)．
• \(1 \leqq M \leqq 400\,000\)．
• \(1 \leqq K \leqq N\)．
• \(1 \leqq U_i < V_i \leqq N\) (\(1 \leqq i \leqq M\))．
• \((U_i, V_i) \neq (U_j, V_j)\) (\(1 \leqq i < j \leqq M\))．
• \(1 \leqq S_j \leqq K\) (\(1 \leqq j \leqq N\))．
• すべての \(l\) (\(1 \leqq l \leqq K\)) について，\(S_j = l\) となる \(j\) (\(1 \leqq j \leqq N)\) が存在する．
• \(1 \leqq Q \leqq 400\,000\)．
• \(1 \leqq A_k \leqq N\) (\(1 \leqq k \leqq Q\))．
• \(1 \leqq B_k \leqq N\) (\(1 \leqq k \leqq Q\))．
• \(A_k \neq B_k\) (\(1 \leqq k \leqq Q\))．
• 入力される値はすべて整数である．

1. (\(5\) 点) \(N \leqq 1\,000\)，\(M \leqq 1\,000\)，\(Q \leqq 1\,000\)．
2. (\(11\) 点) 州 \(l\) (\(1 \leqq l \leqq K\)) に属するすべての都市は，道路と州 \(l\) に属する都市のみを通って互いに行き来できる．
3. (\(42\) 点) \(N \leqq 80\,000\)，\(M \leqq 80\,000\)，\(Q \leqq 80\,000\)．
4. (\(42\) 点) 追加の制約はない．

すべての提出はジャッジシステム上で採点される．

提出されたソースコードは，小課題に対応するすべての採点用入力データについて正しい結果を返したとき，その小課題について正解と認められる．

各提出の得点は，提出されたソースコードについて正解と認められた小課題の得点の合計である．

この課題の得点は，この課題に対するすべての提出の得点の最大値である．

現在の得点は「提出結果」タブの「自分の得点状況」から確認できる．

JOI 2022 · JCIOI · CC BY-SA 4.0

入力は以下の形式で標準入力から与えられる．

\(N\) \(M\) \(K\)
\(U_1\) \(V_1\)
\(U_2\) \(V_2\)
\(\vdots\)
\(U_M\) \(V_M\)
\(S_1\) \(S_2\) \(\cdots\) \(S_N\)
\(Q\)
\(A_1\) \(B_1\)
\(A_2\) \(B_2\)
\(\vdots\)
\(A_Q\) \(B_Q\)

標準出力に \(Q\) 行で出力せよ．\(k\) 行目 (\(1 \leqq k \leqq Q\)) には，\(k\) 番目の交易において特産品を届けることが可能であれば 1 を，不可能であれば 0 を出力せよ．