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
#include <bits/stdc++.h>

using namespace std;
#define ll long long
#define maxn 200010
#define maxa 30
#define maxv 20000
#define result_t pair<bool, pair<int,char>>

//vector<bool> lamps;
vector<pair<int,int>> switches;
unordered_set<int> previous;

bool visited(int now) {
    return previous.find(now) != previous.end();
}

// void run(pair<int, int> switcher, bool val) {
//     lamps[switcher.first] = val;
//     lamps[switcher.second] = val;
// }

void dfs(int now) {
    previous.insert(now);
    for (auto switcher: switches) {
        int mask = (1<<switcher.first) + (1<<switcher.second);
        int switched = now & mask;
        if (switched == 0 || switched == mask) {
            //run(switcher, !current);
            now ^= mask;
            if (!visited(now)) {
                dfs(now);
            }
            now ^= mask;
            //run(switcher, current);
        }
    }
}


int main() {
    int n,m,a,b,lamps=0;
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> n >> m;
    for (int i = 0; i < n; ++i) {
        cin >> a;
        if (a == 1) {
            lamps += (1 << i);
        } 
    }
    for (int i = 0; i < m; ++i) {
        cin >> a >> b;
        switches.push_back({a-1,b-1});
    }
    dfs(lamps);
    cout << (int)previous.size();
}