Shortest Path on the Plane

Special for beginners, ^_^

Problem Description

There are $n$ points on the plane ($n\le100$), each with coordinates in the range $-10000\sim10000$. Some pairs of points are connected by lines.

If there is a connection, one point is reachable from the other; that is, there is a path between the two points, and the length of that path is the straight-line distance between them.

The task now is to find the shortest path from one point to another.

Input Format

The input contains $n+m+3$ lines in total:

The first line is the integer $n$.

Lines $2$ through $n+1$ (exactly $n$ lines) each contain two integers $x$ and $y$, describing the coordinates of one point.

Line $n+2$ is an integer $m$, the number of connections in the graph.

The following $m$ lines each describe one connection, consisting of two integers $i$ and $j$, meaning there is a connection between point $i$ and point $j$.

The last line: two integers $s$ and $t$, the source point and the destination point respectively.

Output Format

One line, a real number (rounded to two decimal places): the length of the shortest path from $s$ to $t$.

Sample Input 1

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

Sample Output 1

3.41

Constraints

1s, 1024KiB for each test case.