#P0815. 四色定理

四色定理

题目描述

四色定理,又称四色地图定理,是一个数学定理:如果在平面上划出一些邻接的有限区域,那么可以用四种颜色来给这些区域染色,使得每两个邻接区域染的颜色都不一样。

现在,给定一块由nn块区域(编号为11~nn)组成的地图以及各区域之间的相邻关系,你的任务是用给出的mm种颜色(编号为11~mm)将地图染色,保证任意两块相邻的区域的颜色都不相同。此外,还有两点限制:

  • 地图中的kk块区域已经涂好了颜色,保证涂好的颜色在11~mm之间,你不需要再改变他们的颜色。

  • 地图中有cc对敌对关系,如果区域uu和区域vv是敌对的关系,那他们的颜色必须不同(注意:互为敌对关系的两块区域不一定相邻)。

请输出合法涂色的方案数。

输入格式

第一行输入两个整数n(1≤n≤10),m(1≤m≤5)n(1 \le n \le 10), m(1 \le m \le 5), 分别表示地图上区域的数量和可用颜色的数量。

接下来nn行,每行输入nn个整数,每个整数为00或11。第ii行第jj列为00表示第ii块区域和第jj块区域不相邻;第ii行第jj列为11表示第ii块区域和第jj块区域相邻。保证第ii行第jj列和第jj行第ii列的数相同,特别的,保证第ii行第ii列的数为00。

接下来输入一行一个整数k1(0≤k1≤n)k1(0 \le k1 \le n),已经染好色的区域数量。

接下来k1k1行,每行输入两个整数x(1≤x≤n),c(1≤c≤m)x(1 \le x \le n), c(1 \le c \le m),表示第xx块区域已经染好了第cc种颜色。

接下来一行一个整数k2(0≤k2≤n×(n−1))k2(0 \le k2 \le n \times (n - 1)),敌对关系的数量。

接下来k2k2行,每行两个整数u,v(1≤u,v≤n,u≠v)u, v(1 \le u, v \le n, u \not=v),表示第uu块区域和第vv块区域为敌对关系。

输出格式

输出一行一个整数,合法染色方案的数量。

样例

7 4
0 1 1 0 1 1 1
1 0 1 1 0 0 0
1 1 0 1 1 0 0
0 1 1 0 1 0 0
1 0 1 1 0 1 1
1 0 0 0 1 0 1
1 0 0 0 1 1 0
3
1 1
6 2
4 1
2
2 5
4 7
4
5 3
0 1 1 1 0
1 0 1 0 1
1 1 0 1 1 
1 0 1 0 1
0 1 1 1 0
2
1 1
5 1
1
1 5
0
5 3
0 1 1 1 0
1 0 1 0 1
1 1 0 1 1 
1 0 1 0 1
0 1 1 1 0
0
0
6

提示

对于样例11,对于样例11,我们假设四种颜色分别为1:红、2:绿、3:蓝、4:黄1:红、2:绿、3:蓝、4:黄,有下面四种合法染色方案:有下面四种合法染色方案:

对于样例22,第11块区域和第55块区域同时染了颜色11,这两块区域还互为敌对,已经不合法,固合法方案数为00。