import sys from collections import deque, Counter input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) inf = 2 ** 63 - 1 mod = 2 #申し訳ありませんでした… class matrix(): r = 1 c = 1 A = None mod = 2 def __init__(self, r, c, mod = 2): self.r = r self.c = c self.A = [[0] * self.c for _ in range(self.r)] if mod is not None: self.mod = mod def makeone(r = 1): A = matrix(r, r, mod) for i in range(r): A[i, i] = 1 return A def __getitem__(self, key): rnow, cnow = key return self.A[rnow][cnow] def __setitem__(self, key, value): rnow, cnow = key self.A[rnow][cnow] = value def __add__(self, other): assert self.r == other.r and self.c == other.c ret = matrix(self.r, self.c) for i in range(self.r): for j in range(self.c): ret[i, j] = self[i, j] + other[i, j] ret[i, j] %= self.mod return ret def __sub__(self, other): assert self.r == other.r and self.c == other.c ret = matrix(self.r, self.c) for i in range(self.r): for j in range(self.c): ret[i, j] = self[i, j] - other[i, j] ret[i, j] %= self.mod return ret def __mul__(self, other): assert self.c == other.r ret = matrix(self.r, other.c) for i in range(self.r): for j in range(self.c): for k in range(other.c): ret[i, k] += self[i, j] * other[j, k] ret[i, k] %= self.mod return ret def augment(self, other): assert self.r == other.r X = matrix(self.r, self.c + other.c, mod = self.mod) for i in range(self.r): for j in range(self.c): X[i, j] = self[i, j] for j in range(other.c): X[i, j + self.c] = other[i, j] return X def diminish(self, c): X = [] for i in range(self.r): X.append((self.A[i][:c])) return matrix(self.r, c, mod = self.mod, A = X) def hakidashi(self): for i in range(self.c): for j in range(i + 1, self.r): if self.A[j][i] != 0: for k in range(self.c): self.A[j][k], self.A[i][k] = self.A[i][k], self.A[j][k] break for i in range(self.r): for j in range(self.c): if self[i, j] != 0: break else: continue K = pow(self[i, j], self.mod - 2, self.mod) for to in range(self.c): self[i, to] *= K self[i, to] %= self.mod for i2 in range(self.r): if i == i2: continue time = self[i2, j] for j2 in range(self.c): self[i2, j2] -= time * self[i, j2] self[i2, j2] %= self.mod return self def inv(self): assert self.c == self.r one = matrix.makeone(r = self.r) new = self.augment(one) new.hakidashi() for i in range(self.r): for j in range(self.c): if i == j: if new[i, j] != 1: return 0, new else: if new[i, j] != 0: return 0, new X = matrix(self.r, self.c) for i in range(self.r): for j in range(self.c): X[i, j] = new[i, j + self.c] return 1, X def lineareq(self, b): assert self.r == b.r assert b.c == 1 Y = self.augment(b) Y = Y.hakidashi() B = [[0] * self.c for _ in range(self.c)] ans = [0] * self.c flag = [0] * self.c for i in range(self.r): j = 0 while j < self.c and Y[i, j] == 0: j += 1 if j == self.c: if Y[i, -1] != 0: return None, None continue flag[j] = 1 ans[j] = Y[i, -1] for k in range(j + 1, self.c): if Y[i, k] % self.mod != 0: B[k][j] = (-Y[i, k])% self.mod flag[k] = -1 for i in range(self.c): if flag[i] != 1: B[i][i] = 1 B=[B[i] for i in range(self.c) if flag[i] != 1] return ans,B def print(self): for v in self.A: print(*v) import sys input = lambda: sys.stdin.readline().rstrip() ii = lambda: int(input()) mi = lambda: map(int, input().split()) li = lambda: list(mi()) INF = 2 ** 63 - 1 mod = 2 n, m = mi() EDGE = [[v - 1 for v in li()] for _ in range(m)] graph = [[] for _ in range(n)] for u, v in EDGE: graph[u].append(v) graph[v].append(u) c = li() A = matrix(n, m) B = matrix(n, 1) for i, V in enumerate(EDGE): u, v = V A[u, i] = 1 A[v, i] = 1 for i in range(n): if c[i] == 1: B[i, 0] = 1 X, Y = A.lineareq(B) if X is None: print(-1) exit() ans = X.count(1) if Y: import random import time t1 = time.time() while time.time() - t1 < 3.5: p = random.randint(0, len(Y) - 1) for i in range(m): X[i] ^= Y[p][i] if ans > X.count(1): ans = min(ans, X.count(1)) elif random.random() < 0.3: for i in range(m): X[i] ^= Y[p][i] print(ans)