Problem Statement

You are given a simple undirected graph, not necessarily connected, consisting of $N$ vertices numbered from $1$ to $N$ and $M$ edges numbered from $1$ to $M$. Edge $i$ connects vertex $a_i$ and vertex $b_i$.

Each vertex is painted either white or black, and the color of vertex $i$ is $c_i$. Here, $c_i=0$ represents white and $c_i=1$ represents black.

You may perform the following operation any number of times, possibly $0$ times. Determine whether it is possible to make all vertices white, and if it is possible, find the minimum number of operations required.

(Operation)
Choose one integer $i$ satisfying $1\leq i \leq M$, and flip the colors of vertex $a_i$ and vertex $b_i $. That is, a black vertex becomes white, and a white vertex becomes black.

Input

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

All inputs are integers and satisfy the following constraints.

• $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$
• If $i \neq j$, then $(a_i, b_i) \neq (a_j, b_j)$
• $c_i$ is $0$ or $1$

Output

Output the minimum number of operations required to make all vertices white.
However, if it is impossible to make all vertices white no matter how many operations are performed, output -1.
Print a newline at the end.

Sample

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

3

Sample 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