Switch Toggling Combinatorics

There are $$N$$ identical switches. Each switch is connected with some other switches such that when a switch is toggled, all of its connected switches also change their state (from on to off, or off to on). Each switch may be toggled at most once.

You are given the connections between the switches, as well as the initial state and the target state of all switches. When a switch is toggled, its state and the states of all switches connected to it flip. The goal is to achieve the target state. Note that the order of toggling does not matter.

Formally, let the state of switch $$i$$ be represented as a bit (0 for off, 1 for on). For each switch $$i$$, if you toggle it (represented by a variable $$x_i=1$$, and $$x_i=0$$ otherwise) then the final state is given by:

$$\text{final}_i = \text{initial}_i + x_i + \sum_{j\in\mathcal{N}(i)} x_j\pmod 2, $$

where $$\mathcal{N}(i)$$ is the set of switches connected with switch $$i$$. You are given the values on the right-hand side as the difference between the target state and the initial state (note that in modulo 2 arithmetic, this difference is 1 if the states differ and 0 if they are the same). Your task is to count the number of ways to choose toggles (each switch toggled at most once) so that all the above equations hold.

inputFormat

The first line contains two integers $$N$$ and $$M$$, where $$N$$ is the number of switches and $$M$$ is the number of connections.

The next $$M$$ lines each contain two integers $$u$$ and $$v$$ (1-indexed) indicating that switch $$u$$ and switch $$v$$ are connected (the connection is bidirectional).

The following line contains $$N$$ integers, representing the initial state of the switches (each either 0 or 1; 0 means off and 1 means on).

The last line contains $$N$$ integers, representing the target state of the switches (each either 0 or 1).

outputFormat

Output a single integer—the number of ways to achieve the target state by toggling switches (with each switch toggled at most once).

sample

3 2
1 2
2 3
0 0 0
1 0 1

1