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
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
#include <iostream>
#include <vector>
#include <set>
#include <deque>

using namespace std;

typedef int NrZarowki;
typedef vector<int> Uklad;

const int MAX_N = 200000;
const int MAX_M = 400000;

int n, m;
vector<NrZarowki> pary[MAX_N];
set<Uklad> osiagniete;
deque<Uklad> kolejka;

template <typename T>
ostream& operator<<(ostream& out, const vector<T>& vec) {
    out << "[ ";
    for (auto v: vec)
        out << v << ", ";
    out << "]";
    return out;
}


void wczytaj_dane() {
    cin >> n >> m;
    Uklad uklad_poczatkowy = vector<int>(n);
    for (int i = 0; i < n; ++i) {
        cin >> uklad_poczatkowy[i];
    }
    osiagniete.insert(uklad_poczatkowy);
    kolejka.push_back(uklad_poczatkowy);

    for (int i = 0; i < m; ++i) {
        int a, b; cin >> a >> b;
        a--; b--;
        if (a < b) {
            pary[b].push_back(a);
        }  else {
            pary[a].push_back(b);
        }
    }
}

vector<Uklad> krok(const Uklad& uklad) {
    vector<Uklad> uklady;
    for (int i = 0; i < n; ++i) {
        for (int j: pary[i]) {
            if (uklad[i] == uklad[j]) {
                Uklad kopia = uklad;
                kopia[i] = 1 - uklad[i];
                kopia[j] = kopia[i];
                uklady.push_back(kopia);
            }
        }
    }
    return uklady;
}

void przeszukaj_przestrzen() {
    while (!kolejka.empty()) {
        Uklad uklad = kolejka.front();
        kolejka.pop_front();
        vector<Uklad> mozliwe_uklady = krok(uklad);
        for (const Uklad& nowy_uklad: mozliwe_uklady) {
            if (osiagniete.find(nowy_uklad) == osiagniete.end()) {
                // takiego ukladu jeszcze nie widzielismy
                osiagniete.insert(nowy_uklad);
                kolejka.push_back(nowy_uklad);
            }
        }
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    wczytaj_dane();
    przeszukaj_przestrzen();
    cout << osiagniete.size() << endl;
    // for (const Uklad& u: osiagniete) {
    //     cout << u << endl;
    // }
    return 0;
}