描述

几乎所有上过计算机科学课的人都熟悉“生命游戏”，即 John Conway 的元胞自动机，其诞生、生存和死亡规则极其简单，却能产生令人惊叹的复杂性。

游戏在一个矩形网格上进行，每个单元格有八个邻居（相邻单元格）。一个单元格要么是活的，要么是死的。由上一代推导下一代的规则为：

• 若一个活细胞周围有 0、1、4、5、6、7 或 8 个活邻居，则该细胞死亡（0、1：孤独；4~8：过度拥挤）。
• 若一个活细胞周围有 2 或 3 个活邻居，则其存活到下一代。
• 若一个死细胞周围有 3 个活邻居，则该位置出生一个新细胞。

多年来，研究人员关注生命游戏中的“伊甸园”（Garden of Eden）配置——那些不可能由任何先前状态演变而来的配置。我们将此扩展为“Efil 游戏”：给定一个当前配置，问它有多少种可能的上一代配置？为简化模型，我们假设网格有限，边缘和角落按环绕方式相邻（即拓扑为环面）。例如，以下 2×3 配置：

恰有三种可能的上一代配置：

注意，在计数邻居时，由于环绕，一个单元格可能因多条路径重复成为同一邻居。以上示例即为此情形。

输入

有多组测试。每组测试首先一行包含两个正整数 $m$ 和 $n$，分别表示配置的行数和列数。下一行包含一个非负整数 $k$，表示当前“活”单元格数。随后 $k$ 行，每行给出一个活细胞的行号和列号（行列均从 0 开始编号）。输入以一行 “0 0” 结束，该行不处理。可假设 $mn\le16$。

输出

对每个测试，用一行输出“Case X: Y possible ancestors.” 或者当 $Y=0$ 时输出“Case X: Garden of Eden.”，模拟下面样例输出。

输入数据 1

2 3
2
0 0
0 1
3 3
4
0 0
0 1
0 2
1 1
3 3
5
0 0
1 0
1 2
2 1
2 2
0 0

输出数据 1

Case 1: 3 possible ancestors.
Case 2: 1 possible ancestors.
Case 3: Garden of Eden.

来源

East Central North America 2005