#include #include using namespace std; using namespace atcoder; using ll=long long; using ld=long double; ld pie=3.141592653589793; ll inf=10010010010010010; ll mod=998244353; int main(){ ll n,m; cin >> n >> m; vectora(m),b(m); for (ll i = 0; i < m; i++) { cin >> a[i] >> b[i]; a[i]--,b[i]--; } vectorc(n); vectortwo(50,1); for (ll i = 1; i < 50; i++) { two[i]=two[i-1]*2; } ll now=0; for (ll i = 0; i < n; i++) { cin >> c[i]; now+=two[i]*c[i]; } mapdp1,dp2; ll x=m/2; for (ll i = 0; i < two[x]; i++) { ll y=now; ll kai=0; for (ll j = 0; j < x; j++) { if (i&two[j]) { y^=two[a[j]]; y^=two[b[j]]; kai+=1; } } if (y==now) { dp1[y]=0; }else{ if (dp1[y]==0) { dp1[y]=kai; }else{ dp1[y]=min(dp1[y],kai); } } } x=m-x; for (ll i = 0; i < two[x]; i++) { ll y=0; ll kai=0; for (ll j = m/2; j < m; j++) { if (i&two[j-m/2]) { y^=two[a[j]]; y^=two[b[j]]; kai+=1; } } if (y==now) { dp2[y]=0; }else{ if (dp2[y]==0) { dp2[y]=kai; }else{ dp2[y]=min(dp2[y],kai); } } } ll ans=inf; for(auto v:dp1){ if (v.first==0) { ans=min(ans,v.second); }else{ if (dp2[v.first]!=0) { ans=min(ans,v.second+dp2[v.first]); } } } if (ans==inf) { cout << -1 << endl; return 0; } cout << ans <