n,m = map(int,input().split())
AB = [[int(x)-1 for x in input().split()] for i in range(m)]
C = list(map(int,input().split()))

ans = m+1

dic = {}
l,r = AB[:m//2],AB[m//2:]
# print(l)
# print(r)
base = 0
for c in C[::-1]:
    base <<= 1
    base |= c
# print(base)
ll = len(l)
for b in range(1<<ll):

    num = base
    count = 0
    for i,(x,y) in enumerate(l):
        if b >> i & 1:
            count += 1
            num ^= 1<<x
            num ^= 1<<y
    # print(num,count)
    if num in dic:
        dic[num] = min(dic[num],count)
    else:
        dic[num] = count

lr = len(r)
for b in range(1<<lr):
    
    num = 0
    count = 0
    for i,(x,y) in enumerate(r):
        if b >> i & 1:
            count += 1
            num ^= 1<<x
            num ^= 1<<y
    # print(num,count)
    if num in dic:
        ans = min(ans,count+dic[num])
if ans == m+1:
    ans = -1
print(ans)