def solve(): N,M=map(int,input().split()) a=[0]*M; b=[0]*M for j in range(M): a[j],b[j]=map(int,input().split()) a[j]-=1; b[j]-=1 c=list(map(int,input().split())) def bit(x,k): return (x>>k)&1 inf=10**9 def calc(F): X={} M=len(F) for S in range(1<<M): p=0 cnt=0 for k in range(M): if bit(S,k): p^=(1<<a[F[k]])^(1<<b[F[k]]) cnt+=1 if cnt<X.get(p,inf): X[p]=cnt return X P=calc(list(range(M//2))) Q=calc(list(range(M//2,M))) target=sum([1<<v for v in range(N) if c[v]==1]) ans=min(P[p]+Q.get(p^target,inf) for p in P) return ans if ans<inf else -1 #================================================== print(solve())