[Poi1997]XOR Gates
时间限制：1s 空间限制：128MB
题目描述
一个异或门有两组输入并产生一组输出：
input 1 input 2 output
0 0 0
0 1 1
1 0 1
1 1 0
如果一个有n个输入1个输出的 由异或门构成的系统 满足下列条件，那么称它为异或网络：
1. 网络的每个输入端和至少一个异或门的输入端相连接
2. 每个异或门的输入端和网络的输入端或者某个异或门的输出端相连
3. 只有一个异或门的输出端和网络的输出端相连
4. 每个异或门的输出端要么和至少一个异或门的输入端相连，要么和网络的输出端相连
5. 存在一个对异或门的编号方式，使得对每个异或门的每个输入端都连接到网络的输入端 或者 一个编号更小的异或门的输出端
例如：
<img src="http://main.edu.pl/images/OI4/xor1.gif" alt="example />
这是个由6个异或门组成的网络，它有5个输入端和1个输出端，并且满足上述所有条件，所以它是个异或网络。注意：上图中的编号并不符合第五个要求，但是确实存在一种编号方法使它满足第五个要求。
一个网络的输入端从1到n编号。每个引脚的高低电位由一个长度为n的01字符串给定。我们假设第i个字符代表着第i个输入引脚的电位。对于每一组输入电位，网络产生一个输出电位，用01表示。注意到每组输入的字符串都是一个代表自然数的二进制串，所以我们可以把输入的字符串按照它们代表的自然数的大小排序。我们会发送固定范围内的自然数到输入端，然后记下有多少次返回了1。
你的任务：
写一个程序：
* 读入关于异或网络的描述：输入引脚数量n，异或门数量m，连接到网络的输出引脚的异或门编号，以及异或门的连接方式
* 读入两个长度为n的二进制串，代表上下区间
* 计算区间内有多少组输入会使网络返回1
* 输出答案
假设 3 <= n <= 100，3 <= m <= 3000，输入门从1到m任意编号。
输入格式
第一行，3个整数：输入引脚数量n，异或门数量m，连接到网络的输出引脚的异或门编号
接下来m行代表异或门的连接方式，在这里的第i行代表第i个异或门的两个输入端，输入在[-n, m]的两个数：如果是-k那么连接到第k个异或门的输入脚，否则连接到输出脚。
最后有两行n位的字符串，代表着上下区间。假设给定的字符串长度不超过 100000
输出格式
一个数：对于给定区间内的输入，有多少个会得到1
样例输入
5 6 5 -1 -2 1 3 1 -2 2 -3 4 6 -4 -5 00111 01110
样例输出
5
提示
没有写明提示
题目来源
没有写明来源