問題文

$1$ から $N$ までの番号がついた $N$ 個の頂点と、$1$ から $M$ までの番号がついた $M$ 本の辺からなる連結とは限らない単純無向グラフが与えられます。辺 $i$ は頂点 $a_i$ と頂点 $b_i$ を結んでいます。

また、各頂点は白か黒のいずれかの色で塗られており、頂点 $i$ の色は $c_i$ です。ただし、 $c_i=0$ は白を、 $c_i=1$ は黒を表します。

あなたは以下の操作を $0$ 回以上何度でも行えます。全ての頂点の色を白にすることができるか判定し、可能な場合は必要な操作回数の最小値を求めてください。

(操作)
$1\leq i \leq M$ を満たす整数 $i$ を一つ選び、頂点 $a_i$ と頂点 $b_i $の色をそれぞれ反転させる。すなわち、頂点の色が黒ならば白に、白ならば黒に変える。

入力

$N~M$
$a_1~b_1$
$\vdots$
$a_{M}~b_{M}$
$c_1~\cdots~c_N$

入力は全て整数で以下の制約を満たす。

• $2\leq N \leq 40$
• $1 \leq M \leq \min\left(\frac{N(N-1)}{2}, 40\right)$
• $1\leq a_i < b_i \leq N$
• $i \neq j$ ならば $(a_i, b_i) \neq (a_j, b_j)$
• $c_i$ は $0$ または $1$

出力

全ての頂点の色を白にするために必要な操作回数の最小値を出力してください。
ただし、何度操作を行なっても全ての頂点の色を白にできないならば-1を出力してください。
最後に改行してください。

サンプル

5 5
1 2
2 3
2 4
4 5
2 5
1 1 1 0 1

3

サンプル2

3 1
1 2
0 1 1

-1

7 9
1 2
1 4
2 3
2 4
3 4
4 5
5 6
5 7
6 7
1 0 1 1 0 0 1

4