Background

Problem Description

There are $N$ identical switches. Each switch is connected to some other switches. Whenever you turn on or turn off a switch, the states of the other switches connected to it will also change accordingly. That is, if a connected switch was on, it becomes off; if it was off, it becomes on.

Your goal is to make the final states of the $N$ switches match a specific target state after performing some switch operations.

For any switch, you can perform the operation on it at most once.

Your task is to compute how many different ways can reach the target state (the order of operations is not counted).

Input Format

The first line contains an integer $K$, meaning there are $K$ groups of testdata.

Each group of testdata is as follows:

The first line: an integer $N$.

The second line: $N$ numbers $0$ or $1$, representing the initial states of the $N$ switches.

The third line: $N$ numbers $0$ or $1$, representing the states of the $N$ switches after all operations.

Then each following line contains two numbers $I, J$, meaning if you operate switch $I$, then the state of switch $J$ will also change.

Each group ends with 0 0.

Output Format

For each group, output one line.

If there is a feasible way, output the total number. Otherwise, output Oh,it's impossible~!!.

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

4
Oh,it's impossible~!!

Hint

For all testdata, $1 \le K \le 10$, $0 < N < 29$.

Translated by ChatGPT 5