hack ケースについて

5/30 現在、3 ケース追加されてます。

問題について

Easy と違う部分をボールドまたは赤文字にしています。とくに入力が変わるので注意してください。

問題文

null たぷにきあ王国が栄え始めたある日、国王の null くんに電流が走りました！しかし国には電気が通っていませんでした！
不便すぎるのでとりあえず発電所とお城だけでも早急に繋ぎたいと思い、null くんははあなたに電線の消費量の試算を任せました。

電線の消費量は使用した電線候補の長さの和とします。
$N$ 個の電柱 $1, 2, \dots, N$ があり、$i(1 \le i \le N)$ 番目の電柱の座標は $(p_i, q_i)$ です。
$M$ 個の電線候補があり、$j(1 \le j \le M)$ 番目の電線候補は電柱 $P_j$ と電柱 $Q_j$ を線分で結んだものです。
電線はこの候補にしかつけられません。
つけられた電線をいくつかたどることで電柱 $A$ から電柱 $B$ にたどり着くとき、電柱 $A$ と電柱 $B$ は繋がっているといいます。
電線候補をすべて使用したとき、すべての電柱が使われ、繋がることが保証されます。
また、自分から自分への電線候補がないこと、ある $2$ つの電柱を結ぶ電線候補は高々 $1$ つであることが保証されます。
あなたの仕事は発電所である電柱 $X$ とお城である電柱 $Y$ を繋げる時の電線の消費量が小さい順に $K$ つ試算することです。ただし、一つの試算中に同じ電柱を二回使うことはできません。
また、電線候補は一筆書きができる必要があります。(21:46 追記)

入力

$N\ M\ \color{red}{K}$
$X\ Y$
$p_1\ q_1$
$p_2\ q_2$
$\dots$
$p_N\ q_N$
$P_1\ Q_1$
$P_2\ Q_2$
$\dots$
$P_M\ Q_M$

$2 \le N \le \color{red}{2 \times 10^3}$
$\color{red}{1 \le K \le 10}$
$N - 1 \le M \le min(\frac{N(N - 1)}{2}, \color{red}{2 \times 10^3})$
$1 \le X, Y \le N$
$X \neq Y$
$-10^3 \le p_i, q_i \le 10^3$
$1 \le P_j, Q_j \le N$
電線候補をすべて使用したとき、すべての電柱が使われ繋がることが保証される。
自分から自分への電線候補がないこと、ある $2$ つの電柱を結ぶ電線候補は高々 $1$ つであることが保証される。
入力はすべて整数である。

出力

電柱候補をいくつか使い電柱 $X$ と電柱 $Y$ を繋げるときの電線の消費量が小さい順に $K$ つ電線使用量を出力してください。同じ距離の経路が複数ある場合、一つの経路で一つとカウントします。
絶対誤差または相対誤差の小さいほうが $10^{-4}$ まで許容されます。
最後に改行してください。

サンプル

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

2.828427

5 8 5
2 4
0 0
-1 -1
1 -1
1 1
-1 1
1 2
1 3
1 4
1 5
2 3
3 4
4 5
5 2

2.828427
4.000000
4.000000
4.828427
4.828427

2 1 10
1 2
0 0
0 1
1 2

1.000000
-1
-1
-1
-1
-1
-1
-1
-1
-1

2 1 2
1 2
0 0
0 0
1 2

0.000000
-1