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
//Brut na szybko

#include <iostream>
#include <vector>
#include <set>
using namespace std;

vector<pair<int, int>> switches; // Przechowuje pary żarówek, na które wpływają przełączniki
set<vector<int>> configurations; // Zestaw unikalnych konfiguracji, które można osiągnąć

// Funkcja rekurencyjna do sprawdzania wszystkich możliwych konfiguracji
void checkConfigurations(vector<int> &bulbs, int index)
{
	if (index == switches.size())
	{
		configurations.insert(bulbs); // Dodajemy aktualną konfigurację do zestawu unikalnych konfiguracji
		return;
	}

	// Rekurencyjne sprawdzenie bez użycia obecnego przełącznika
	checkConfigurations(bulbs, index + 1);

	// Stan żarówek przed zmianą
	int bulb1 = switches[index].first, bulb2 = switches[index].second;
	if (bulbs[bulb1] == bulbs[bulb2])
	{
		// Zmieniamy stany żarówek, jeśli obie są w tym samym stanie
		bulbs[bulb1] = !bulbs[bulb1];
		bulbs[bulb2] = !bulbs[bulb2];

		// Sprawdzamy konfiguracje po zmianie
		checkConfigurations(bulbs, index + 1);

		// Przywracamy poprzednie stany, aby kontynuować sprawdzanie innych kombinacji
		bulbs[bulb1] = !bulbs[bulb1];
		bulbs[bulb2] = !bulbs[bulb2];
	}
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);

	int n, m;
	cin >> n >> m;
	vector<int> bulbs(n);
	for (int i = 0; i < n; ++i) cin >> bulbs[i]; // Początkowe stany żarówek
	for (int i = 0; i < m; ++i)
	{
		int a, b;
		cin >> a >> b;
		switches.emplace_back(a - 1, b - 1); // Przełączniki wpływają na pary żarówek, indeksowanie od 0
	}

	checkConfigurations(bulbs, 0); // Rozpoczęcie sprawdzania z początkowym indeksem przełącznika jako 0

	cout << configurations.size() << endl; // Wypisanie liczby unikalnych konfiguracji
	return 0;
}