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
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> VI;
typedef pair <int,int> ii;
typedef long long LL;
#define pb push_back
const int INF = 2147483647;
const int N = 3005;

int n, m, r, i, a, b;
vector<ii> ed;
set<int> s, ss;

void go(int w) {
	if (s.find(w) != s.end()) return;
	//printf("%d\n", w);
	s.insert(w);
	for (auto& ww : ed) {
		int a = n - 1 - ww.first;
		int b = n - 1 - ww.second;
		bool o1 = ((w & (1<<a)) > 0);
		bool o2 = ((w & (1<<b)) > 0);
		//printf("%d %d %d %d\n", a, b, o1, o2);
		if (o1 == o2) {
			if (o1) go(w - (1<<a) - (1<<b)); else go(w + (1<<a) + (1<<b));
		}
	}
}

int comb(int a, int b) {
	LL res = 1;
	for (int i=1;i<=a;i++) res *= i;
	for (int i=1;i<=b;i++) res /= i;
	for (int i=1;i<=a-b;i++) res /= i;
	return res;
}

void loop() {
	int a = 1;
	while (a < 10) {
		a++;
		a--;
	}
}

int main() {
scanf("%d %d", &n, &m);
r = 0;
for (i=0;i<n;i++) {
	scanf("%d", &a);
	r = r * 2 + a;
}
bool isTree = (m == n - 1);
while (m--) {
	scanf("%d %d", &a, &b);
	ed.pb(ii(a - 1, b - 1));
}
go(r);
printf("%d\n", s.size());
/*for (auto& w : s) {
	std::string binary = std::bitset<7>(w).to_string();
	printf("%d %s\n", w, binary.c_str());
}
bool ok = 0;
if (isTree) {
	for (i=0;i<=n/2;i++) if (s.size() == comb(n, i)) ok = 1;
} else ok = (s.size() == (1<<(n - 1)));
//if (!ok) loop();*/
return 0;
}