부대의 무장 해제

먼 나라의 이야기다. 이 나라에서는 ACM과 ICPC라는 두 무장 세력이 오랫동안 내전을 벌였다. 그러나 오늘 10월 21일, 두 세력의 화해가 승인되었다. 두 세력의 역사에서 전환점이 된 날이다.

이 나라의 도로는 모두 가로 방향이거나 세로 방향이다. 도로의 끝점마다, 그리고 두 도로가 만나는 교차점마다 마을이 하나씩 있다. 한 지점에 마을이 둘 생기는 일은 없다. 일부 마을에는 ACM이나 ICPC의 부대가 주둔한다. 화해로 이 부대는 모두 필요 없어졌으므로, 검증할 수 있는 방식으로 동시에 무장을 해제해야 한다. 무장 해제는 각 세력에 지정된 마을에서만 이루어지고, 한 마을에서 무장을 해제하는 부대는 하나뿐이다. 그래서 부대를 옮겨야 한다.

이 임무의 지휘는 당신이 맡는다. 명령 한 번으로 움직이는 부대는 하나다. 부대는 지금 서 있는 마을을 지나는 도로 하나를 골라, 그 도로 위의 다른 마을로 이동한다. 가는 길에 지나는 마을과 도착하는 마을은 모두 비어 있어야 한다. 다른 부대가 서 있는 마을은 지나갈 수도 없고 그 마을에서 멈출 수도 없다. 이동이 끝나기 전에는 다음 명령을 내릴 수 없다.

화해가 승인되었어도 부대원은 여전히 예민해서 쉽게 전투를 벌인다. 그래서 서로 다른 세력의 부대는 같은 도로 위의 마을에 함께 서 있을 수 없다. 이 조건은 명령과 명령 사이의 배치를 두고 판정하므로, 부대가 지나가기만 한 마을은 따지지 않는다. 또 한쪽에만 명령하면 그 세력이 불만을 품으므로, 두 세력에 번갈아 명령해야 한다. 어느 세력에 먼저 명령할지는 당신이 고른다.

모든 ACM 부대가 ACM 지정 마을에 서고 모든 ICPC 부대가 ICPC 지정 마을에 서면 임무가 끝난다. 임무를 끝내는 데 필요한 명령의 최소 횟수를 구하는 프로그램을 작성하라.

입력은 여러 데이터 집합으로 이루어진다. 각 데이터 집합의 형식은 다음과 같다.

n mA mI
rx(1,1) ry(1,1) rx(1,2) ry(1,2)
...
rx(n,1) ry(n,1) rx(n,2) ry(n,2)
sxA(1) syA(1)
...
sxA(mA) syA(mA)
sxI(1) syI(1)
...
sxI(mI) syI(mI)
txA(1) tyA(1)
...
txA(mA) tyA(mA)
txI(1) tyI(1)
...
txI(mI) tyI(mI)

$n$은 도로의 수다. $m_A$와 $m_I$는 각각 ACM과 ICPC의 부대 수다 ($m_A > 0$, $m_I > 0$, $m_A + m_I < 8$). rx(i,1) ry(i,1)과 rx(i,2) ry(i,2)는 $i$번째 도로의 두 끝점이고, 이 도로는 항상 x축이나 y축과 평행하다. sxA 줄은 ACM 부대가 처음 서 있는 마을, sxI 줄은 ICPC 부대가 처음 서 있는 마을이다. txA 줄은 ACM 부대가 무장을 해제할 수 있는 마을, txI 줄은 ICPC 부대가 무장을 해제할 수 있는 마을이다.

다음을 가정해도 된다.

• 도로의 끝점과 교차점을 합친 마을의 수는 18개를 넘지 않는다.
• 가로 도로끼리는 서로 닿지도 겹치지도 않는다. 세로 도로끼리도 마찬가지다.
• 모든 마을은 도로로 연결되어 있다.
• 처음 배치에서 ACM 부대와 ICPC 부대가 같은 도로 위의 마을에 함께 서 있는 경우는 없다.
• 모든 좌표는 0 이상 100 이하의 정수다.
• 데이터 집합은 50개 이하다.

입력의 끝은 0이 세 개인 줄로 표시하며, 이 줄은 처리하지 않는다.

각 데이터 집합마다 필요한 명령의 최소 횟수를 한 줄에 출력한다. 임무를 끝내는 방법이 적어도 하나 있음이 보장된다.