题目描述

在冬季，这个最饥饿和严酷的时期，洞螈（Holedox）会在它的巢穴中冬眠。当春天来临，洞螈醒来，向它巢穴的出口移动，爬出巢穴，开始它新的生活。

洞螈是一种特殊的蛇，不过它的身体并不是很长。它的巢穴就像一个迷宫，可以想象成一个 \(n\times m\) 的方格矩形。每个方格要么是石头，要么是空地，只有空地允许洞螈在里面移动。用巢穴中的行号和列号组成的有序对来表示，出口所在的方格位置是 \((1,1)\)。

洞螈的身体长度为 \(L\)，可以逐块表示。设 \(B_1(r_1,c_1)\)、\(B_2(r_2,c_2)\)、\(\cdots\)、\(B_L(r_L,c_L)\) 表示它长度为 \(L\) 的身体，其中对于 \(1\leq i\leq L - 1\)，\(B_i\) 在巢穴中与 \(B_{i + 1}\) 相邻，\(B_1\) 是它的头部，\(B_L\) 是它的尾部。

为了在巢穴中移动，洞螈会选择其头部相邻的一个空地，这个空地既不是石头也没有被它的身体占据。然后它将头部移动到这个空地上，同时，它身体的其他每一块都会移动到相应的前一块所占据的方格中。

例如，在图2中，一开始洞螈的身体可以表示为 \(B_1(4,1)\)、\(B_2(4,2)\)、\(B_3(3,2)\)、\(B_4(3,1)\)。在下一个步骤中，观察到 \(B_1'(5,1)\) 是头部唯一可以移动到的方格，洞螈将它的头部移动到 \(B_1'(5,1)\)，然后将 \(B_2\) 移动到 \(B_1\) 的位置，\(B_3\) 移动到 \(B_2\) 的位置，\(B_4\) 移动到 \(B_3\) 的位置。因此，在一步之后，洞螈的身体位于 \(B_1(5,1)\)、\(B_2(4,1)\)、\(B_3(4,2)\)、\(B_4(3,2)\)（见图3）。

给定巢穴的地图以及洞螈身体每一块的初始位置，你的任务是编写一个程序，计算出洞螈将其头部移动到出口方格 \((1,1)\) 所需的最少步数。

输入

输入由若干个测试用例组成。每个测试用例的第一行包含三个整数 \(n\)、\(m\) （\(1\leq n, m\leq20\)）和 \(L\) （\(2\leq L\leq8\)），分别表示巢穴的行数、巢穴的列数以及洞螈的身体长度。接下来的 \(L\) 行每行包含一对行号和列号，表示洞螈身体从 \(B_1(r_1,c_1)\) 到 \(B_L(r_L,c_L)\) 每一块的初始位置，其中 \(1\leq r_i\leq n\)，\(1\leq c_i\leq m\)，\(1\leq i\leq L\)。下一行包含一个整数 \(K\)，表示巢穴中石头方格的数量。接下来的 \(K\) 行每行包含一对行号和列号，表示每一个石头方格的位置。然后用一个空行分隔不同的测试用例。

输入以一行包含三个 \(0\) 的行作为结束标志。

注意：\(B_i\) 总是与 \(B_{i + 1}\) 相邻（\(1\leq i\leq L - 1\)），并且出口方格 \((1,1)\) 永远不会是石头。

输出

对于每个测试用例，输出一行，包含测试用例的编号，后面跟着洞螈必须采取的最少步数。如果该测试用例没有解决方案，则输出“\(-1\)”。

输入示例

5 6 4
4 1
4 2
3 2
3 1
3
2 3
3 3
3 4

4 4 4
2 3
1 3
1 4
2 4
4

2 1
2 2
3 4
4 2

0 0 0

输出示例

Case 1: 9
Case 2: -1

提示

在上述示例测试用例中，洞螈的头部可以按照 ((4,1)$\to$(5,1)$\to$(5,2)$\to$(5,3)$\to$(4,3)$\to$(4,2)$\to$(4,1)$\to$(3,1)$\to$(2,1)$\to$(1,1)) 的路径移动到出口方格，步数最少，为九步。

来源

2002年北京竞赛