import sys
input = sys.stdin.readline
from collections import *

N, M = map(int, input().split())
edges = [tuple(map(int, input().split())) for _ in range(M)]
c = list(map(int, input().split()))
M1 = M//2
M2 = M-M1
pair = defaultdict(lambda: 10**18)

for S in range(1<<M1):
    mask = 0
    cnt = 0
    
    for i in range(M1):
        if (S>>i)&1:
            u, v = edges[i]
            mask ^= 1<<(u-1)
            mask ^= 1<<(v-1)
            cnt += 1
    
    for v in range(N):
        if c[v]==1:
            mask ^= 1<<v
    
    pair[mask] = min(pair[mask], cnt)

ans = 10**18

for S in range(1<<M2):
    mask = 0
    cnt = 0
    
    for i in range(M2):
        if (S>>i)&1:
            u, v = edges[M1+i]
            mask ^= 1<<(u-1)
            mask ^= 1<<(v-1)
            cnt += 1

    ans = min(ans, cnt+pair[mask])
        
if ans==10**18:
    print(-1)
else:
    print(ans)