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
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
#include <cstdio>
#include <map>
#include <unordered_set>
#include <string>
#include <vector>

typedef long long int i64;
const i64 MOD = 1000000009LL;

struct Node {
  int grouped;
  int state;
  std::vector<int> n;
}g[200200];

void _dfs(int i, int epoch, std::map<int, int> &acc) {
  g[i].grouped = epoch;
  acc[i] = g[i].state;
  for (int n : g[i].n) {
    if (g[n].grouped == -1) {
      _dfs(n, epoch, acc);
    }
  }
}

std::string to_str(std::map<int, int> &val) {
  std::string ret = "";
  for (auto &p : val) {
    ret.append(std::to_string(p.first)).append(p.second ? "#" : "-");
  }
  return ret;
}

void from_str(std::string & val, std::map<int, int>& ret) {
  int n = 0;
  for(int i = 0; val[i]; ++i) {
    if (val[i] != '#' && val[i] != '-') {
      n *= 10;
      n += val[i] - '0';
    } else {
      ret[n] = (val[i] == '#') ? 1 : 0;
      n = 0;
    }
  }
}

i64 group(int i, int epoch) {
  std::map<int, int> gr;
  _dfs(i, epoch, gr);

  std::unordered_set<std::string> all_states;
  std::unordered_set<std::string> new_states;
  std::string ss = to_str(gr);
  new_states.insert(ss);
  all_states.insert(ss);

  while(!new_states.empty()) {
    std::unordered_set<std::string> states;
    for(const std::string & s: new_states) {
      states.insert(s);
    }
    new_states.clear();
    for(auto st: states) {
      gr.clear();
      from_str(st, gr);
      for (auto pair : gr) {
        for (int nei : g[pair.first].n) {
          if (gr[nei] == pair.second) {
            gr[pair.first] = 1-gr[pair.first];
            gr[nei] = 1 - gr[nei];
            std::string new_state = to_str(gr);
            if (!all_states.contains(new_state)) {
              new_states.insert(new_state);
              all_states.insert(new_state);
            }
            gr[pair.first] = 1-gr[pair.first];
            gr[nei] = 1 - gr[nei];
          }
        }
      }
    }
  }
  return all_states.size();
}

int main() {
  i64 result = 1;
  int N, M, a, b;
  scanf("%d%d", &N, &M);

  for (int i = 0; i < N; ++i) {
    g[i].grouped = -1;
    scanf("%d", &g[i].state);
  }

  for (int i = 0; i < M; ++i) {
    scanf("%d%d", &a, &b);
    --a, --b;
    g[a].n.push_back(b);
    g[b].n.push_back(a);
  }

  int epoch = 0;
  for (int i = 0; i < N; ++i) {
    if (g[i].grouped == -1) {
      result = result * group(i, epoch++) % MOD;
    }
  }
  printf("%lld\n", result);
}