1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
#include <vector>
#include <cstdio>
#include <stack>
#include <algorithm>
#include <queue>
#include <map>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <set>
#include <cstring>
#include <bitset>
#include <iostream>
#include <queue>
#include <iomanip>
#include <complex>

using namespace std;

#define ALL(x) x.begin(), x.end()
#define UNIQUE(c) (c).resize(unique(ALL(c)) - (c).begin())
#define FOR(i, a, b) for(int i =(a); i <=(b); ++i)
#define RE(i, n) FOR(i, 1, n)
#define RED(i, n) FORD(i, n, 1)
#define FORD(i, a, b) for(int i = (a); i >= (b); --i)
#define REP(i, n) for(int i = 0;i <(n); ++i)
#define REPD(i, n) FORD(i, n-1,0)

const int maxn = 400012, mod = 1000000007, bis = 4096;
int n, m, a[maxn], po, st,x,y, res;
pair<int, int>pa[maxn];
bitset<100000000>odw;
void dfs(int ak) {
    odw[ak] = true;
    res ++;
    REP(i, m)if(((ak>>pa[i].first) & 1) == ((ak>>pa[i].second) & 1)){
        auto pom = ak;
        pom ^= (1<<pa[i].first);
        pom ^= (1<<pa[i].second);
        if(!odw[pom])dfs(pom);
    }
}
void solve() {
    cin>>n>>m;
    po = 1;
    REP(i, n){
        cin>>a[i];
        if(a[i])st+=po;
        po *= 2;
    }
    REP(i, m){
        cin>>x>>y;
        pa[i] = {--x, --y};
    }
    dfs(st);
    cout<<res<<"\n";
}

int main() {
    ios_base::sync_with_stdio(false), cin.tie(nullptr);
    int tt = 1;
//    cin >> tt;
    while (tt--) {
        solve();
    }
    return 0;
}