第21回日本情報オリンピック　二次予選

2022年2月5日
情報オリンピック日本委員会

問題文

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

制約

• 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)．
• 入力される値はすべて整数である．

小課題

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

採点に関する注意

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

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

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

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

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

入力

入力は以下の形式で標準入力から与えられる．
N M K
U₁ V₁
U₂ V₂
:
U_M V_M
S₁ S₂ … S_N
Q
A₁ B₁
A₂ B₂
:
A_Q B_Q

出力

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

入出力例

入力例 1
4 3 2
1 2
2 3
3 4
1 2 1 2
3
1 2
1 3
1 4

出力例 1
1
0
1

• 1 番目の交易は，州 1 または州 2 に属する都市のみを通って，都市 1 から都市 2 に特産品を輸送するというものである．都市 1 → 都市 2 と輸送すれば条件を満たすので，1 を出力する．
• 2 番目の交易は，州 1 に属する都市のみを通って，都市 1 から都市 3 に特産品を輸送するというものである．条件を満たす輸送経路は存在しないので，0 を出力する．
• 3 番目の交易は，州 1 または州 2 に属する都市のみを通って，都市 1 から都市 4 に特産品を輸送するというものである．都市 1 → 都市 2 → 都市 3 → 都市 4 と輸送すれば条件を満たすので，1 を出力する．

この入力例は小課題 1, 3, 4 の制約を満たす．

入力例 2
4 2 1
1 3
2 4
1 1 1 1
4
1 2
1 3
2 3
2 4

出力例 2
0
1
0
1

この入力例は小課題 1, 3, 4 の制約を満たす．

入力例 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

出力例 3
1
0
1
1

この入力例はすべての小課題の制約を満たす．

入力例 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

出力例 4
1
1
0
1
0
1
1
1
1
1

この入力例は小課題 1, 3, 4 の制約を満たす．