# Problem F

Flygskam

*gasp*) air. Skylar had scolded friends and family for flying, heavily handing out the recent Swedish export

*flygskam*(verbatim translation: flight shame). But alas, the things we do for love! Now they want your help to calculate the minimum amount of

*flygskam*Skylar will accumulate on a one-way trip across the globe.

To calculate the best route you models the planet as a perfect sphere and assumes that all flights fly at the distance $6381$ km from the center of the earth. The amount of shame for a single point-to-point flight is calculated as the distance between the airports in km, plus a take-off and landing penalty of $100$, that is, two airports with the flight distance $1000$ km will result in $1100$ shame.

## Latitude and longitude

The positions of the airports are given as the latitude and
longitude in (decimal) degrees. The latitude of a point
$P$ on the earths surface
is the angle between the equatorial plane and a line passing
through $P$ and the center
of the earth. The equator has latitude $0^\circ $, points north of the
equator has positive values and points south of the equator has
negative values, the North Pole has latitude $90^\circ $ and the South Pole
latitude $-90 ^\circ $.
Half circles that run from the North to the South pole are
called *meridians*. The zero meridian runs
through Greenwich. The longitude of a point $Q$ is the angle between the zero
meridian plane and the line that run through $Q$ and the center of the earth, with
values from $- 180^\circ $
to $+180^\circ $, with
positive values east of Greenwich.

## Input

Input starts with one line with two integers $1 \leq N \leq 10\, 000$, the number of airports and $1 \leq M \leq 100\, 000$, the number of two-way flight routes. The second line has two strings $S$ and $T$, Skylar’s start position and Skylar’s target position. Then follows $N$ lines, each starts with a three letter (uppercase) airport code, followed by two real values numbers, the latitude and longitude in degrees. Then follows $M$ lines, each with two strings $a$ and $b$, the airports with a two-way flight connection.

All flight airports have unique names and all connections are between existing airports.

## Output

Output a real value with the minimum amount of *flygskam* Skylar will obtain on a one-way trip. If
the target is unreachable and Skylar will be forever alone,
output -1. Answers within a relative or absolute error of
$10^{-6}$ will be
accepted.

Sample Input 1 | Sample Output 1 |
---|---|

4 4 ARN SCR ARN 59.6467921 17.9370443 SCR 61.156603 12.837360 CPH 55.618023 12.650763 OSL 60.197646 11.100008 ARN OSL ARN CPH SCR OSL OSL CPH |
729.09706162045 |

Sample Input 2 | Sample Output 2 |
---|---|

2 1 LAX AKL AKL -37.006131 174.783781 LAX 33.941589 -118.408531 LAX AKL |
10603.3297338597 |

Sample Input 3 | Sample Output 3 |
---|---|

4 2 CDG AKL AKL -37.006131 174.783781 CDG 49.014490 2.542102 DXB 25.253176 55.365673 LAX 33.941589 -118.408531 CDG LAX DXB AKL |
-1 |