Sightseeing

Mark and his younger sister want to tour several landmarks in a city. Their map shows the landmarks (with their coordinates) and the streets that connect them. Every street is either for walking or for biking. Mark loves biking, so he travels only on biking streets, while his sister, who dislikes biking, travels only on walking streets. Both of them start their trip at the central station and finish at the west station; both stations are landmarks that appear on the map.

Each night, every traveller camps at the landmark they are currently visiting, and the two talk over a pair of two-way radios. A radio costs more the larger its coverage range is, so the siblings want to choose their routes (Mark's biking route and his sister's walking route) so that the required coverage range is as small as possible.

On every night each of them stays at exactly one landmark: on the first night both are at the central station, and on the last night both are at the west station. Each following morning, each traveller either moves along their route to an adjacent landmark or stays one more day where they are (they move independently, so both may move on the same day). A call on a given night is possible only if the Euclidean distance between the two travellers does not exceed the radio's coverage range. Minimize the largest distance between the two over all nights.

The input contains several test cases; each test case is a graph that models a map.

The first line of each test case contains two non-negative integers $n$ ($n \le 50$), the number of vertices, and $m$, the number of edges. Each of the next $n$ lines gives the coordinates $x$ and $y$ of the vertex whose id is $i$ (on the $i$-th line). The following $m$ lines describe the edges; each line has the two vertex ids of an edge followed by a single character, W or B. W marks a walking street and B marks a biking street. Two landmarks may be joined by both a walking street and a biking street. The last line gives the ids of the central station and the west station, in this order.

You may assume there is always both a walking route and a biking route between the central and west stations. Every number in the input is a non-negative integer smaller than $10^4$. The input terminates with 0 0.

For each test case, print on a single line the square of the minimum required radio coverage range.