Switch Puzzle

Problem Background

POJ 1830

Problem Description

There are $n$ identical switches. Each switch is linked to some other switches. Whenever you turn a switch on or off, all switches linked to it change their states as well: if a linked switch was on, it becomes off; if it was off, it becomes on.

Your goal is, after several operations, to bring the $n$ switches to a specific target state. For any switch, you may operate it at most once.

Your task is to count how many ways there are to reach the specified state (the order of operations does not matter).

Input Format

The first line contains an integer $k$, meaning there are $k$ test cases below.

Each test case is formatted as follows:

The first line contains an integer $n$.

The second line contains $n$ integers, the initial states of the $n$ switches ($0$ = off, $1$ = on).

The third line contains $n$ integers, the desired states of the $n$ switches after all operations ($0$ = off, $1$ = on).

Then each following line contains two integers $i, j$, meaning that if you operate switch $i$, switch $j$'s state also changes (one-way). Each test case ends with 0 0.

Output Format

If there is at least one valid way, output the total number of ways; otherwise output $-1$.

Sample Input

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

Sample Output

4
-1

Sample Explanation

Explanation of the first test case: there are four ways — operate switch 1, operate switch 2, operate switch 3, or operate switches 1, 2 and 3 together.

Constraints

For $100\%$ of the data: $1 \leq k \leq 10$, $2 \leq n \leq 28$, $1 \leq i, j \leq n$, $i \neq j$, the pair $(i,j)$ may repeat, and the total number of relation lines $\leq n^2$.