Shortest Shopping Trip

On Zhongshan Road, there are n stores (with n \leq 100) located at coordinates within the range \([-10000, 10000]\). Among these, there are m connections between some pairs of stores. If there is a connection between two stores, it means one can travel between them directly, and the distance of this connection is the Euclidean distance between the two points, i.e., \(\sqrt{(x_i-x_j)^2+(y_i-y_j)^2}\).

The input provides four integers in the first line: \(n\), \(m\), \(s\), and \(t\), where \(s\) and \(t\) are the starting and target stores (1-indexed). The next \(n\) lines list the coordinates of the stores, and the following \(m\) lines each contain two integers \(u\) and \(v\) indicating a bidirectional connection between store \(u\) and store \(v\).

Your task is to calculate the shortest distance from store \(s\) to store \(t\) using the existing connections, and output the result with a precision of 6 decimal places. If store \(t\) is not reachable from store \(s\), output -1.

inputFormat

The first line contains four space-separated integers: n m s t.

• n (\(1 \leq n \leq 100\)): the number of stores.
• m: the number of connections between stores.
• s and t: the start and target store indices (1-indexed).

The next n lines each contain two integers x and y (\(-10000 \leq x, y \leq 10000\)) indicating the coordinates of the stores.

The following m lines each contain two space-separated integers u v (1-indexed) representing a bidirectional road between store u and store v. The distance of the connection is defined as the Euclidean distance between the corresponding points.

outputFormat

Output the shortest distance from store s to store t with exactly 6 decimal places. If there is no valid path from s to t, output -1.

sample

4 4 1 4
0 0
0 1
1 0
1 1
1 2
2 3
3 4
1 4

1.000000