/* -*- coding: utf-8 -*-
 *
 * 2236.cc:  No.2236 Lights Out On Simple Graph - yukicoder
 */

#include<cstdio>
#include<unordered_map>
#include<algorithm>
 
using namespace std;

/* constant */

const int MAX_N = 40;
const int MAX_M = 40;
const int MAX_K = MAX_M / 2;
const int KBITS = 1 << MAX_K;
const int INF = 1 << 30;

/* typedef */

using ll = long long;
using umli = unordered_map<ll,int>;

/* global variables */

ll es[MAX_M];

/* subroutines */

/* main */

int main() {
  int n, m;
  scanf("%d%d", &n, &m);

  for (int i = 0; i < m; i++) {
    int u, v;
    scanf("%d%d", &u, &v);
    u--, v--;
    es[i] = (1LL << u) | (1LL << v);
  }

  ll st = 0;
  for (int i = 0; i < n; i++) {
    int ci;
    scanf("%d", &ci);
    st |= (ll)ci << i;
  }

  int k0 = m / 2, k1 = m - k0;
  int kbits0 = 1 << k0, kbits1 = 1 << k1;

  umli scs0, scs1;
  for (int bits = 0; bits < kbits0; bits++) {
    ll s = 0;
    int c = 0;
    for (int i = 0, bi = 1; i < k0; i++, bi <<= 1)
      if (bits & bi) s ^= es[i], c++;
    if (! scs0.count(s)) scs0[s] = c;
    else scs0[s] = min(scs0[s], c);
  }
  for (int bits = 0; bits < kbits1; bits++) {
    ll s = 0;
    int c = 0;
    for (int i = 0, bi = 1; i < k1; i++, bi <<= 1)
      if (bits & bi) s ^= es[k0 + i], c++;
    if (! scs1.count(s)) scs1[s] = c;
    else scs1[s] = min(scs1[s], c);
  }
  //for (auto [s, c]: scs0) printf(" %lld,%d", s, c); putchar('\n');
  //for (auto [s, c]: scs1) printf(" %lld,%d", s, c); putchar('\n');

  int minc = INF;
  for (auto [s0, c0]: scs0) {
    ll s1 = st ^ s0;
    if (scs1.count(s1)) minc = min(minc, c0 + scs1[s1]);
  }

  printf("%d\n", (minc < INF) ? minc : -1);
  
  return 0;
}