헥스웜프의 헥서펜트

헥스웜프(Hexwamp)는 정육각형 모양의 홈(dimple)이 빈틈없이 깔린 기이한 늪이다. 헥서펜트(hexerpent)는 이 환경에 적응한 뱀으로, 정육각형 마디들이 사슬처럼 이어진 몸을 가진다. 각 마디는 홈 하나에 꼭 맞게 들어가며, 사슬에서 이웃한 두 마디는 항상 서로 인접한 홈에 놓인다.

헥서펜트는 자기 마디 중 일부를, 각 마디가 있던 홈에서 인접한 홈으로 옮기며 기어간다. 몸이 끊어지면 안 되므로, 이동하기 전에 인접해 있던 두 마디는 이동한 뒤에도 인접해 있어야 한다. 어떤 마디가 움직일 때, 사슬에서 그 마디와 이웃한 마디들은 이동을 받쳐 주어야 하므로 같은 순간에 함께 움직일 수 없다. 서로 인접하지 않은 마디들이라면 몇 개든 동시에 움직일 수 있다.

그 결과, 몸의 양 끝에 있는 마디(머리 또는 꼬리)는 최대 두 개의 홈으로 옮겨 갈 수 있고, 중간 마디는 움직일 수 있더라도 최대 한 개의 홈으로만 옮겨 갈 수 있다.

예를 들어 장애물이 없다면 헥서펜트는 그림 C-1(왼쪽에서 오른쪽 순서)처럼 몸을 비틀며 앞으로 기어갈 수 있다. 이 그림에서 뱀은 여덟 마디 중 네 마디를 한 번에 움직이며, 이런 이동을 네 번 하면 홈 한 칸만큼 전진한다. 사실 헥서펜트는 사이드와인더처럼 옆으로 기는 데에 훨씬 능하다.

그림 C-1: 앞으로 기어가기

이들의 피부는 매우 끈적여서, 사슬에서 이웃하지 않은 두 마디가 인접한 홈에 놓이게 되면(그림 C-2) 서로 달라붙어 뱀이 죽고 만다. 물론 두 마디가 같은 홈에 함께 들어갈 수도 없다. 이 규칙들은 뱀의 이동을 더욱 제약한다. 그래서 먹이가 머리 바로 옆 홈에 있어도 그것을 얻기 위해 애를 써야 할 때가 있다.

그림 C-2: 치명적인 경우

헥스웜프에는 곳곳에 바위도 있으며, 각 바위는 홈 하나를 차지한다. 헥서펜트의 피부는 바위에는 달라붙지 않지만, 어떤 마디도 바위가 있는 홈으로는 들어갈 수 없다. 바위를 피하느라 이동이 더 제약되지만, 뱀들은 지형을 훤히 꿰고 있어 언제나 가장 빠른 경로를 찾아낸다.

당신은 이 늪과 뱀을 연구하는 과학자 팀을 이끌고 있으며, 단 한 명의 희생자도 내지 않고 연구를 마쳐야 한다. 당신이 할 일은, 사람을 잡아먹는 헥서펜트가 머리(첫 번째 마디)를 늪에 있는 과학자의 위치로 옮기는 데 얼마나 빨리 도달할 수 있는지 추정하는 것이다. 위험한 것은 머리뿐이며, 첨단 방착 슈트를 입은 과학자는 머리를 제외한 몸통 마디와는 같은 홈에 안전하게 있을 수 있다.

입력은 여러 개의 데이터셋으로 이루어지며, $0$ 하나만 있는 줄로 끝난다. 데이터셋의 개수는 $10$을 넘지 않는다.

각 데이터셋의 형식은 다음과 같다.

n
x1 y1
x2 y2
...
xn yn
k
u1 v1
u2 v2
...
uk vk
X Y

첫 줄에는 헥서펜트의 마디 수 $n$ ($2 \le n \le 8$)이 주어진다. 이어지는 $n$개의 줄에는 각 마디의 좌표 $x$와 $y$가 머리부터 꼬리까지 순서대로 주어진다.

그다음 줄에는 늪에 있는 바위의 수 $k$ ($0 \le k \le 100$)가 주어진다. 이어지는 $k$개의 줄에는 각 바위의 좌표 $u$와 $v$가 주어진다.

마지막 줄에는 과학자가 서 있는 목표 홈의 좌표를 나타내는 두 정수 $X$와 $Y$가 주어진다. 뱀의 머리는 처음에 이 위치에 있지 않다.

모든 좌표 $x$, $y$, $u$, $v$, $X$, $Y$는 $-999999$ 이상 $999999$ 이하의 정수이다. 한 줄에 있는 두 정수는 공백 하나로 구분된다. 위치를 나타내는 좌표계는 그림 C-3과 같다.

그림 C-3: 좌표계

헥스웜프의 헥서펜트

문제

입력

출력