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
//
//  main.cpp
//  zar
//
//  Created by Michał Kowalski on 16/03/2024.
//

#include <stdio.h>
#include <vector>
#include <iostream>
#include <unordered_map>
#include <queue>
using namespace std;
void remove_alone_edges(vector<pair<int, int> > & m, string & V);
int N,M;

unordered_map<string, bool> U;
queue<string> Q;
int edges[200005];


int main() {
    scanf("%d %d",&N,&M);
    string V;
    V.reserve(N+1);
    for (int i=0;i<N;++i) {
        int t;
        scanf("%d",&t);
        V.append(t == 1 ? "1" : "0");
    }
    vector<pair<int, int> > moves;
    moves.reserve(M+1);
    for (int i=0;i<M;++i) {
        int a,b;
        scanf("%d %d",&a,&b);
        --a;
        --b;
        edges[a]++;
        edges[b]++;
        moves.push_back(make_pair(a, b));
    }
    remove_alone_edges(moves,V);
    Q.push(V);
    U[V] = true;
    while(!Q.empty()) {
        string state = Q.front();
        Q.pop();
        for(auto move: moves) {
            if (state[move.first] == state[move.second]) {
                string newState = state;
                char bit = state[move.first];
                bit = bit == '0' ? '1' : '0';
                newState[move.first] = bit;
                newState[move.second] = bit;
                if (!U.contains(newState)) {
                    U[newState] = true;
                    Q.push(newState);
                }
            }
        }
    }
    printf("%d\n",(U.size() % (1000000007)));
    return 0;
}

void remove_alone_edges(vector<pair<int, int> > & m, string & V) {
    for(auto x = m.begin();x<m.end();) {
        int a = (*x).first;
        int b = (*x).second;
        if (edges[a] == 1 && edges[b] == 1 && V[a] != V[b]) {
            m.erase(x);
        } else {
            x++;
        }
    }
}