問題
会津国の若松平野に、集落が点在していました。いくつかの集落の間はまっすぐで互いに行き来できる道で繋がっていて、平野にあるどの集落の間も道を辿って行き来ができます。それぞれの道には長さに応じた維持費がかかりますが、すべての集落が資金を出し合って道を維持していました。
あるとき、すべての集落が一つの村にまとまることが決まり、村を囲む境界線を引くことになりました。国の決まりでは、村を構成するどの２つの集落を結んだまっすぐな線も、村の外を通ってはいけません（境界線上を通ることは許されます）。さらに、会津国では村を囲む境界線上に道がなければなりません。境界線上に道がない場所には、国が新たに道を作ってくれます。
しかし、道の維持費は村が支払うので、村人達は境界線をできるだけ短くしたいと考えています。さらに、村人達はすべての集落の間を行き来できる状態を維持しつつ、境界線上にない道を廃止することで、道の長さの合計を最小にすることにしました。
集落の位置と元々あった道の情報が与えられる。境界線上に道を置き、かつ、すべての集落が行き来できるようにした場合の、道の長さの合計の最小値を計算するプログラムを作成せよ。ただし、集落は大きさのない点、道は幅のない線分とする。
入力
入力は以下の形式で与えられる。
V R x1 y1 x2 y2 : xV yV s1 t1 s2 t2 : sR tR
１行目に集落の数 V (3 ≤ V ≤ 100) と道の数 R (2 ≤ R ≤ 1000) が与えられる。
続く V 行に集落を表す点の情報が与えられる。各行に与えられる２つの整数 xi, yi (-1000 ≤ xi, yi ≤ 1000)は、それぞれ i 番目の集落の x 座標、y座標を表す。
続く R 行に元々あった道の情報が与えられる。各行に与えられる２つの整数 si, ti (1 ≤ si < ti ≤ V)は、i 番目の道が si 番目の集落と ti 番目の集落をつないでいることを表す。
入力は以下の条件を満たす。
- i ≠ j ならば、i 番目の集落と j 番目の集落の座標は異なる。
- どの２つの集落についても、それらを直接結ぶ道は高々１つしか現れない。
- ２つの異なる道が端点以外の点を共有することはない。
- ３つ以上の集落が同一直線上に並んでいることはない。
出力
条件を満たす道の長さの合計の最小値を１行に実数で出力する。ただし、誤差がプラスマイナス 0.001 を超えてはならない。この条件を満たせば小数点以下何桁表示してもよい。
入出力例
入力例 1
5 5 0 0 1 1 3 0 3 2 0 2 1 2 2 3 2 4 3 4 1 5
出力例 1
11.4142
入力例 2
7 6 0 2 3 0 2 2 1 0 4 1 2 3 3 5 1 3 2 4 2 3 3 5 3 7 6 7
出力例 2
18.2521