관광

마크와 여동생은 한 도시의 여러 명소를 둘러보려고 한다. 두 사람이 가진 지도에는 명소(각 명소의 좌표 포함)와 명소를 잇는 거리들이 표시되어 있다. 각 거리는 걷기 전용이거나 자전거 전용이다. 마크는 자전거를 좋아해 자전거 거리로만 이동하고, 자전거를 싫어하는 여동생은 걷기 거리로만 이동한다. 두 사람은 모두 중앙역에서 출발해 서부역에서 여정을 마친다. 두 역은 모두 지도에 있는 명소다.

매일 밤, 두 사람은 각자 그때 머무는 명소에서 야영하며 한 쌍의 양방향 무전기로 서로 안부를 나눈다. 무전기는 통달 거리(coverage range)가 클수록 값이 비싸므로, 두 사람은 각자의 경로(마크의 자전거 경로와 여동생의 도보 경로)를 잘 골라서 필요한 통달 거리를 최대한 작게 하려고 한다.

각 밤마다 두 사람은 각자 정확히 하나의 명소에 머문다. 첫 밤에는 둘 다 중앙역에, 마지막 밤에는 둘 다 서부역에 있다. 이후 매일 아침 각자는 자신의 경로를 따라 이웃한 다음 명소로 이동하거나, 지금 있는 명소에 하루 더 머물 수 있다(두 사람은 독립적으로 움직이므로 같은 날 둘 다 이동할 수도 있다). 어떤 밤에 통화가 가능하려면 두 사람 사이의 유클리드 거리가 무전기의 통달 거리를 넘지 않아야 한다. 모든 밤에 걸친 두 사람 사이 거리의 최댓값을 최소로 만들어라.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 테스트 케이스는 지도를 나타내는 그래프다.

각 테스트 케이스의 첫 줄에는 정점의 수 $n$ ($n \le 50$)과 간선의 수 $m$이 음이 아닌 정수로 주어진다. 이어지는 $n$개의 줄 중 $i$번째 줄에는 번호가 $i$인 정점의 좌표 $x$와 $y$가 주어진다. 그다음 $m$개의 줄은 각 간선을 나타내며, 각 줄은 간선의 양 끝 정점 번호 두 개와 문자 하나 W 또는 B로 이루어진다. W는 걷기 거리, B는 자전거 거리를 뜻한다. 두 명소 사이에 걷기 거리와 자전거 거리가 모두 존재할 수도 있다. 마지막 줄에는 중앙역과 서부역의 정점 번호가 차례로 주어진다.

중앙역과 서부역 사이에는 걷기 경로와 자전거 경로가 항상 모두 존재한다고 가정해도 된다. 입력에 등장하는 모든 수는 $10^4$보다 작은 음이 아닌 정수다. 입력은 0 0으로 끝난다.

각 테스트 케이스마다, 필요한 최소 무전기 통달 거리의 제곱을 한 줄에 출력한다.