Description

There are shops everywhere along Zhongshan Road, which has become a point of no return for the shopaholic guru "Love-and-Sorrow" (Ai Yu Chou). There are $n$ ($n \leq 100$) shops on Zhongshan Road, and each shop’s coordinates lie between $-10000$ and $10000$. Among them, there are $m$ roads connecting pairs of shops. If there is a road, you can travel from one shop to the other, and the length of the road is the straight-line distance between the two points. Now the guru "Love-and-Sorrow" wants to find the shortest distance between two shops. Can you help compute it?

Input Format

A total of $n+m+3$ lines:

The first line: an integer $n$.

The next $n$ lines: each line contains two integers $x$ and $y$, giving the coordinates of a shop.

The next line: an integer $m$.

The next $m$ lines: each line describes a road, consisting of two integers $i$ and $j$, indicating there is a road between shop $i$ and shop $j$.

The next line: two integers $s$ and $t$, indicating the source shop and the target shop, respectively.

Output Format

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

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

3.41

Hint

Constraints: For $100 \%$ of the testdata: $2 \le n \leq 100$, $1 \le i, j, s, t \le n$, $1 \le m \leq 1000$.

Translated by ChatGPT 5