/* -*- coding: utf-8 -*- * * 2236.cc: No.2236 Lights Out On Simple Graph - yukicoder */ #include #include #include 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; /* 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; }