223. XOR门

【题目描述】

一个XOR门包含两个输入和一个输出，它的工作可以用下表描述：

input 1 input 2 output
0         0        0
0         1        1
1         0        1
1         1        0

如果一个XOR门系统有n个输入和1个输出，且满足以下条件，则称这个XOR门系统为XOR网络。

1. 系统的每一个输入都至少与一个XOR门的输入端相连；
2. 系统中每个门的输入必须与系统的一个输入或另一个门的输出连接；
3. 有且只有有一个门的输出与系统的输出相连；
4. 每个门的输出要与另外至少一个门的输入或系统的输出相连；
5. 这些XOR门存在一种编号方式，使得每个门的输入都与系统的输入或具有较小编号的门的输出相连。

例子：

图中有一个由6个XOR门组成的XOR系统。它有5个输入和1个输出，它满足以上的5个条件，所以它是一个XOR网络。注意：图中给出的编号方式不满足条件5，但可以找到一种满足条件的编号方式。

网络的输入标号为1到5，一种输入状态可以用一个长度为n的字符串表示，每一位是0或1，我们假设第I个数字表示第I个输入的状态。每一个 输入都是一个自然数的二进制编码，所以我们可以按输入状态表示的数值的大小将它们排序。我们要测试一个电路门网络，通过向它发送一个范围以内的输入，计算 使输出是1的输入个数。

任务：

1. 从文本文件xor.in中读入电路网的的描述。描述包括输入的个数n，XOR门的个数m，以及XOR门连接的情况。
2. 从文件中读入两个长度为n的二进制串，表示输入的上限和下限。
3. 计算给定范围内有多少种输入可以使输出为1。
4. 将结果写入文件xor.out。

我们假设3 < n < 100, 3 < m < 3000，而且网络中的门是用1到m之间的数任 意编号的。

【输入格式】

第一行包含三个整数，分别表示输入的个数，门的个数，连接到输出的门的编号。以下的m行描述网络中的连接情况。第I行表示第I个门的两个输入，两个输 入为范围[-n,m]之间的一个整数。如果输入是网络的第k个输入，则连接的描述是一个整数－k，如果输入是第j个门，则连接的描述是一个整数j。以下两 行各有一个n位二进制串，表示输入的上限和下限。我们假设给定范围内最多100000种输入。

【输出格式】

输出文件包含一个整数，表示给定范围内有多少种输入可以使输出为1。

【输入样例】

5 6 5
-1 -2
1 3
1 -2
2 -3
4 6
-4 -5
00111
01110

【输出样例】

5