問題文

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 点) 追加の制約はない．

採点に関する注意

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

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

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

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

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

入力例 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 の制約を満たす．