#P0815. 四色定理
四色定理
题目描述
四色定理,又称四色地图定理,是一个数学定理:如果在平面上划出一些邻接的有限区域,那么可以用四种颜色来给这些区域染色,使得每两个邻接区域染的颜色都不一样。
现在,给定一块由块区域(编号为~)组成的地图以及各区域之间的相邻关系,你的任务是用给出的种颜色(编号为~)将地图染色,保证任意两块相邻的区域的颜色都不相同。此外,还有两点限制:
-
地图中的块区域已经涂好了颜色,保证涂好的颜色在~之间,你不需要再改变他们的颜色。
-
地图中有对敌对关系,如果区域和区域是敌对的关系,那他们的颜色必须不同(注意:互为敌对关系的两块区域不一定相邻)。
请输出合法涂色的方案数。
输入格式
第一行输入两个整数, 分别表示地图上区域的数量和可用颜色的数量。
接下来行,每行输入个整数,每个整数为或。第行第列为表示第块区域和第块区域不相邻;第行第列为表示第块区域和第块区域相邻。保证第行第列和第行第列的数相同,特别的,保证第行第列的数为。
接下来输入一行一个整数,已经染好色的区域数量。
接下来行,每行输入两个整数,表示第块区域已经染好了第种颜色。
接下来一行一个整数,敌对关系的数量。
接下来行,每行两个整数,表示第块区域和第块区域为敌对关系。
输出格式
输出一行一个整数,合法染色方案的数量。
样例
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
提示
对于样例,对于样例,我们假设四种颜色分别为,有下面四种合法染色方案:有下面四种合法染色方案:

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