푸른 숲

존은 콘솔 게임 "Tales of Algorithmers"를 하고 있고, 이제 마지막 던전인 푸른 숲 앞에 서 있다. 던전을 가장 빨리 지나는 길을 찾으려고 존은 층마다 지도를 그렸다.

각 층은 연결된 단순 평면 그래프다. 정점은 x 좌표와 y 좌표로 주어지는 점이고, 간선의 길이는 두 끝점 사이의 유클리드 거리다. 정점에는 일방통행 워프 게이트가 놓여 있기도 하다. 게이트를 쓰면 다른 층일 수도 있는 다른 정점으로 이동하며, 게이트로 이동한 거리는 0으로 친다. 한 정점에 놓인 게이트는 많아야 하나지만, 같은 정점을 목적지로 삼는 게이트는 여럿일 수 있다.

존은 층마다 지도를 한 장씩 그렸다고 생각했다. 다 그리고 나서야 몇 가지 실수를 알아차렸다. 같은 층을 여러 번 그렸을 수도 있고, 어떤 게이트는 지도에 빠뜨렸을 수도 있다. 다만 모든 게이트를 적어도 한 장에는 그려 넣었다는 사실은 확실하다. 그래서 같은 층의 지도를 한 장으로 합치면 그 층의 게이트가 모두 드러난다. 모양이 같은 층은 없으므로, 합칠 수 있는 두 지도는 같은 층의 지도다. 또한 회전 대칭인 층도 없으므로 정삼각형이나 정사각형 모양의 층은 나오지 않는다.

지도 B를 회전과 평행이동만으로 지도 A에 겹칠 수 있으면 두 지도를 합칠 수 있다. 뒤집기는 허용하지 않는다. 게이트는 빠져 있을 수 있으므로 합칠 수 있는지 판정할 때는 게이트를 따지지 않는다. 지도 A와 지도 B를 합치면 지도 B의 정점과 그 정점이 겹치는 지도 A의 정점은 같은 정점이다. 그러므로 지도 B에 그린 게이트는 대응하는 지도 A 정점에 놓인 게이트로 보고, 게이트의 목적지도 같은 방식으로 옮겨 읽는다. 그 뒤에는 지도 B를 잊어도 된다. 합친 두 지도가 같은 정점에 게이트를 가지고 있으면 두 게이트의 목적지도 같다.

합친 지도를 써서 던전 입구에서 출구까지 가는 최단 경로의 길이를 구하라.

입력은 여러 개의 데이터셋으로 이루어지며, 데이터셋은 최대 50개다. 각 데이터셋의 형식은 다음과 같다.

n
component1
component2
...
componentn
es ev
xs xv

n은 지도의 개수이고, componenti는 i번째 지도를 다음 형식으로 나타낸다.

A
x1 y1
x2 y2
...
xA yA
B
s1 d1
s2 d2
...
sB dB
C
g1 m1 v1
g2 m2 v2
...
gC mC vC

A는 지도의 정점 개수이고, 이어지는 A개의 줄에는 각 정점의 x 좌표와 y 좌표가 주어진다. B는 간선의 개수이고, 이어지는 B개의 줄에는 간선 하나의 두 끝점이 주어진다. C는 워프 게이트의 개수이고, 이어지는 C개의 줄에는 게이트가 놓인 정점, 그리고 그 게이트가 이어지는 지도 번호와 정점 번호가 주어진다. 지도의 정점 번호와 지도 번호는 모두 1부터 시작한다.

n개의 지도 뒤에 오는 es ev 줄은 입구가 es번 지도의 ev번 정점에 있다는 뜻이고, xs xv 줄은 출구가 xs번 지도의 xv번 정점에 있다는 뜻이다.

모든 데이터셋은 다음 조건을 만족한다.

• $1 \le n \le 50$
• $3 \le A \le 20$
• $A - 1 \le B \le A(A-1)/2$
• $0 \le C \le A$
• $-10000 \le x_i, y_i \le 10000$

마지막 데이터셋 다음에는 0 하나만 있는 줄이 온다.

각 데이터셋마다 입구에서 출구까지 가는 최단 경로의 길이를 소수점 아래 여섯 자리로 반올림해 출력한다. 경로가 없으면 -1을 출력한다.