Zju1361Holedox Moving

一条蛇被困在洞穴中，需要移动到位于坐标 $(1,1)$ 的出口。请计算蛇的头部到达出口所需的最少步数。

洞穴可以看作一个 $N\times M$ 的网格。蛇由 $L$ 个依次相连的部位组成，相邻两个部位必须位于上下左右相邻的网格中。

每一步中，蛇的头部可以移动到上下左右相邻的一个网格，其余每个部位依次移动到前一个部位移动前所在的位置。蛇不能移动到有石头的网格中，也不能与自身的任何部位重合。

输入格式

输入包含多组数据。

每组数据的第一行包含三个整数 $N$、$M$、$L$，其中 $N$ 和 $M$ 表示洞穴的大小，$L$ 表示蛇的长度。

接下来 $L$ 行，每行包含两个整数，依次给出蛇从头部到尾部各个部位的坐标。第 $1$ 组坐标表示蛇头的位置，第 $L$ 组坐标表示蛇尾的位置。

随后一行包含一个整数 $K$，表示洞穴中的石头数量。

接下来 $K$ 行，每行包含两个整数，表示一块石头的坐标。

相邻两组数据之间有一个空行。输入以 0 0 0 结束。

输出格式

对于第 $i$ 组数据，如果蛇可以到达出口，则输出 Case i: x，其中 $x$ 表示蛇头到达坐标 $(1,1)$ 所需的最少步数；如果无法到达，则输出 Case i: -1。

每组数据输出一行，数据编号 $i$ 从 $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),(5,1),(5,2),(5,3),(4,3),(4,2),(4,1),(3,1),(2,1),(1,1)。$

因此，最少需要移动 $9$ 步。

数据范围

• $1\le N,M\le 20$；
• $1\le L\le 8$；
• $0\le K\le NM-L$；
• 所有坐标 $(x,y)$ 均满足 $1\le x\le N$、$1\le y\le M$；
• 蛇的各个部位占据互不相同的坐标；
• 各块石头占据互不相同的坐标，且不会与蛇身重合；
• 出口 $(1,1)$ 处没有石头。

来源与许可

本题题面与测试数据整理自 BZOJ。

样例 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