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
#include <iostream>
#include <queue>
#include <vector>

const uint32_t bn = 1e9 + 7; // Duża liczba.
const uint32_t pow_2_15 = 32768;

void add_edge(std::vector<uint32_t> adj[], uint32_t u, uint32_t v) 
{
  // Uwaga. Pozwala dodać wielokrotną krawędź (ale tu takich nie ma).
  adj[u].push_back(v);
  adj[v].push_back(u);
}

//void print_graph(std::vector<uint32_t> adj[], uint32_t V)
//{
//  for (uint32_t v = 0; v < V; ++v) 
//  {
//    std::cout << "vertex " << v << " ";
//    for (uint32_t i = 0; i < adj[v].size(); i++)
//      std::cout << " -> " << adj[v][i];
//    std::cout << "\n";
//  }
//  std::cout << "\n";
//}

void check_subgraph(std::vector<uint32_t> adj[],
                    uint8_t c[],  
                    uint32_t n, 
                    uint32_t v, 
                    bool checked[], 
                    uint32_t &sub_size,
                    bool &press_works) 
{  
  // Sprawdza spójny podgraf, zwracając jego rozmiar i to, czy przyciski 
  // zadziałają.
  std::vector<bool> visited(n, false);
  std::queue<uint32_t> q;
  q.push(v);
  visited[v] = true;
  sub_size = 1;
  press_works = false;
  checked[v] = true;
  while (!q.empty()) 
  {
    uint32_t current = q.front();
    q.pop();
    for (std::vector<uint32_t>::iterator it = adj[current].begin();
         it != adj[current].end(); it++)
    {
      if (c[*it] == c[current])
        press_works = true;
      if (!visited[*it]) 
      {
        visited[*it] = true;
        checked[*it] = true;
        sub_size++;
        q.push(*it);
      }
    }
  }
}

int main() 
{
  std::ios_base::sync_with_stdio(false);
  std::cin.tie(NULL); 
  uint32_t n, m;
  std::cin >> n >> m;
  uint8_t c[n];
  bool checked[n];
  for (uint32_t i = 0; i < n; ++i) 
  {
    std::cin >> c[i];
    checked[i] = false;        
  }
  std::vector<uint32_t> adj[n];
  for (uint32_t i = 0; i < m; ++i) 
  {
    uint32_t a, b;
    std::cin >> a >> b;
    add_edge(adj, a - 1, b - 1);  
  }
  // print_graph(adj, n);
  // Zakładamy, że w każdej spójnej składowej jest co najmniej jedna krawędź, 
  // która łączy dwa wierzchołki o tym samym stanie. W przeciwnym razie 
  // przełączniki nie działają.
  uint32_t sub_size, press_works_cnt = 0;
  bool press_works;
  for (uint32_t i = 0; i < n; i++)
  {
    if (!checked[i])
    {
      check_subgraph(adj, c, n, i, checked, sub_size, press_works);
      if (press_works)
        press_works_cnt += sub_size;
    }  
  }  
  uint32_t bits_m_1 = press_works_cnt - 1;
  uint32_t result = 1;
  uint32_t div15 = bits_m_1 / 15, mod15 = bits_m_1 % 15;
  for (int i = 0; i < div15; i++)
    result = (result * pow_2_15) % bn;
  for (int i = 0; i < mod15; i++)  
    result = (result * 2) % bn;
  std::cout << result << "\n";  
  // system("pause");
  return 0;
}