Bulb Switches

This problem is adapted from PA 2024 Runda 5 problem Żarówki ("Bulbs") – many thanks to Macaronlin for the translation.

There are n bulbs, each having two states: ON or OFF. The initial state of each bulb is given. There are also m switches; each switch controls exactly two bulbs. When you press a switch, if the two bulbs it controls are in the same state, both bulbs change to the opposite state; if they are in different states, nothing happens.

You are allowed to press the switches in any order and as many times as you like. Two configurations are considered different if there is at least one bulb that is ON in one configuration and OFF in the other. Determine the number of different configurations that can be achieved.

Note: In each move, the operation is reversible – pressing a switch when its two bulbs have the same state will flip both bulbs, and the move may later be undone by pressing the same switch again. However, a switch can only be used when the two bulbs it controls currently share the same state.

Hint: The switches interact only with the two bulbs they control. Hence, one can decompose the bulbs into connected components (where bulbs are connected if there is a sequence of switches linking them) and analyze the state‐space on each component by performing a breadth–first search (or other state–space exploration) on all possible configurations that may be reached from the initial state. Then, the final answer is the product of the number of reachable configurations in each component.

inputFormat

The first line contains two integers n and m (1 ≤ n ≤ 16, 0 ≤ m ≤ n(n-1)/2), representing the number of bulbs and the number of switches.

The second line contains n integers (each 0 or 1) separated by spaces, indicating the initial state of each bulb (0 for OFF, 1 for ON).

Each of the next m lines contains two integers u and v (1 ≤ u, v ≤ n, u ≠ v) indicating that there is a switch controlling bulbs u and v.

outputFormat

Output a single integer – the number of different configurations that can be reached by pressing the switches arbitrarily many times.

sample

2 1
0 0
1 2

2