#119. 开关问题

开关问题

题目描述

n 个开关有初态和目标状态。操作某个开关时,该开关及其所有被影响的开关翻转。每个开关至多操作一次,操作顺序不区分。求能够达到目标状态的操作集合数量。

输入格式

首行测试组数。每组为 n、n 个初态、n 个目标态;之后逐行输入 i、j,表示操作 i 影响 j,以0 0结束该组关系。n<29。

输出格式

每组输出方案数;无解输出 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~!!

题意整理;原题与输入输出格式对照。