홀레독스 이동

홀레독스는 미로에 사는 작은 뱀이다. 미로는 $n \times m$ 칸으로 이루어진 격자이며, 각 칸은 돌이거나 빈 칸이다. 홀레독스는 빈 칸으로만 이동할 수 있다. 각 칸은 (행, 열)로 나타내며, 미로의 출구는 칸 (1, 1)이다.

홀레독스의 몸은 길이가 $L$이고, 블록 단위로 $B_1(r_1, c_1)\ B_2(r_2, c_2)\ \ldots\ B_L(r_L, c_L)$와 같이 표현한다. 모든 $1 \le i \le L-1$에 대해 $B_i$는 $B_{i+1}$과 인접하며, $B_1$은 머리, $B_L$은 꼬리이다.

한 번 이동할 때, 홀레독스는 머리와 인접한 칸 중에서 비어 있는 칸 하나를 고른다. 즉 그 칸은 돌이 아니어야 하고, 꼬리를 포함하여 몸의 어떤 블록도 현재 그 칸을 차지하고 있지 않아야 한다. 머리를 그 칸으로 옮기면서, 동시에 나머지 모든 블록은 자기 바로 앞 블록이 방금 떠난 칸으로 미끄러져 들어간다. 즉 $B_2$는 $B_1$이 있던 칸으로, $B_3$은 $B_2$가 있던 칸으로, 이런 식으로 $B_L$까지 이동한다.

예를 들어 몸이 $B_1(4,1)\ B_2(4,2)\ B_3(3,2)\ B_4(3,1)$이라고 하자. 머리가 이동할 수 있는 칸이 $(5,1)$뿐이라면, 한 번 이동한 뒤 몸은 $B_1(5,1)\ B_2(4,1)\ B_3(4,2)\ B_4(3,2)$가 된다.

미로와 홀레독스의 모든 블록의 처음 위치가 주어질 때, 머리가 출구 (1, 1)에 도달하기 위해 필요한 최소 이동 횟수를 구하여라.

입력은 여러 개의 테스트 케이스로 이루어진다.

각 테스트 케이스의 첫 줄에는 세 정수 $n$, $m$ ($1 \le n, m \le 20$)과 $L$ ($2 \le L \le 8$)이 주어진다. 각각 미로의 행 수, 열 수, 홀레독스의 몸 길이이다. 이어지는 $L$개의 줄에는 각각 행과 열이 주어지며, $B_1(r_1,c_1)$부터 $B_L(r_L,c_L)$까지의 처음 위치를 순서대로 나타낸다. 이때 $1 \le r_i \le n$, $1 \le c_i \le m$이다. 다음 줄에는 돌의 개수 $K$가 주어지고, 이어지는 $K$개의 줄에는 각 돌의 행과 열이 주어진다.

인접한 테스트 케이스는 빈 줄로 구분된다. 입력의 끝은 세 개의 0으로 이루어진 줄로 표시된다.

$1 \le i \le L-1$인 모든 $i$에 대해 $B_i$는 $B_{i+1}$과 인접함이 보장되며, 출구 칸 (1, 1)은 절대 돌이 아니다.

각 테스트 케이스마다 한 줄에 Case X: S를 출력한다. 여기서 $X$는 테스트 케이스 번호(1부터 시작)이고, $S$는 머리가 출구에 도달하기 위한 최소 이동 횟수이다. 머리가 출구에 절대 도달할 수 없으면 $S$ 자리에 -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)$이며, 이동 횟수는 9이다. 머리가 처음에 $(3,1)$로 이동할 수 없음에 유의하라. 그 칸은 곧 꼬리가 떠날 칸이지만, 이동하는 순간에는 여전히 꼬리가 차지하고 있기 때문이다.