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

constexpr int MAXN = 200009;
vector< pair<int, int> > switches; 
unordered_map<string, bool> odw;
int dif[2], ans = 0;

void Find(string &s){
    if(odw[s] == 1) return;
    odw[s] = 1;
    ans++;
    for(auto x : switches){
        if(s[x.first] == s[x.second]){
            s[x.first] = s[x.second] = dif[s[x.first]];
            Find(s);
            s[x.first] = s[x.second] = dif[s[x.first]];
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    string s;
    dif[0] = 1; dif[1] = 0;
    int n, m;
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        bool b; cin >> b;
        s.push_back(b);
    }
    for(int i = 0; i < m; i++){
        int a, b;
        cin >> a >> b;
        switches.push_back({a - 1, b - 1});
    }
    Find(s);
    cout << ans;
    return 0;
}