問題文

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

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

JOI 合衆国の産業大臣である K 理事長は，これから $Q$ 回の交易を行う予定である．$k$ 回目 ($1 \le k \le Q$) の交易は，都市 $A_k$ から都市 $B_k$ へ，いくつかの道路と都市を経由して特産品を運ぶというものである．ただし，この交易には州 $S_{A_k}$ と州 $S_{B_k}$ ($S_{A_k} = S_{B_k}$ のときは州 $S_{A_k}$) のみが協力しており，これらの州以外の都市を経由すると特産品が盗まれてしまう．

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

制約

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

小課題

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

入力

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

N M K
U_1 V_1
U_2 V_2
:
U_M V_M
S_1 S_2 ... S_N
Q
A_1 B_1
A_2 B_2
:
A_Q B_Q

出力

標準出力に，$Q$ 行で出力せよ．$k$ 行目 ($1 \le k \le 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
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

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

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

1
1
0
1
0
1
1
1
1
1

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