Hamako Online Judge

誤差
1e-3

TLE
1sec

MLE
256MB

得点
50

Magic.03 『Shout Her Name!!』

前回のあらすじ

アヤの協力の下、傷を癒したヒナは、幻想郷の現状を知る。
どうやら、保たれていた平穏に、闇が差し込もうとしているらしい。
コティーヤを止めるべく、幸せを取りもどすべく、
再び立ち上がろうとするヒナの前に、
空間を裂いて、声が聞こえた。

本編

？？？
「立ち上がって、それでどうするの？
今のあなたでは、前と同じように、惨敗するだけだわ。」

空間を裂いて現れたのは、可愛らしい少女であった。
しかし、その可愛らしい風貌からは、世の理を知った賢者のようなオーラが放たれていた。

アヤ
「あなたまさか…、ユカリン？
幻想郷の幻想に潜むと何万年も前から語り継がれている…」

ヒナ
「それで、そんな人がどうしてここに…？」

ユカリン
「あなた、コティーヤ達を止めたいのでしょう？
その為には、しなければならないことがある。
私はそれを行うために、あなたを訪ねたの。」

ヒナ
「しなければいけないこと？
秘密の修行とか？私ワクワクするわ！！」

アヤ
「相変わらずマイペースねぇ。
それでユカリン、ヒナは何をする必要があるのかしら？」

ユカリン
「ヒナ、よく聞きなさい。
あなたの身体には、災いと福を司る一つの因子が散らばっている。
それを、〔厄倖因子〕と呼ぶわ。
厄倖因子はお互いに繋がっているものもあるわ。
私の力によって福と厄の二つの状態に分けることが出来る。
あなたの身体は今、全ての因子が厄になっている。
この状態では、あなたの持つ本来の力を引き出すことはできないわ。
だから、私が情報を書き換える。
厄の因子と福の因子を繋げたときに、
厄同士、もしくは福同士が繋がってない因子の集合体を作ることが出来ることがある。
これがあなたの力の源になるわ。
そして、条件を満たす因子の集合体を結界で囲む。
こうすることで、あなたの力は目覚める。
分かったかしら？」

ヒナ
「わかんないや！！取り敢えずお願い！！」

問題

さぁ、目覚めの刻は来た。
彼女の力が覚醒する為に必要な条件を纏めよう。

ヒナは厄倖因子を持っている。
厄倖因子は、繋がりを持つものがある。
厄倖因子は、福と厄の二状態を持つ。
ユカリンは、可能ならば、福同士、厄同士が繋がらないように状態を設定する。
この状態を満たす因子の集合体全てを、辺の数が最小となる結界一つで囲む。
結界内に、条件を満たさない因子が入っていても構わない。
結界は、直線から成る多角形で作られる。
結界は、座標と座標を繋ぐ形で張られる。
結界は、場合によっては直線になったり、点になることがある。

そしてヒナの力は放たれる。

厄倖因子の数、各座標、繋がりが与えられるので、
厄倖因子の状態を任意の状態に設定したときの、
ヒナの力の源に成りうることが可能な厄倖因子の数の最大と、
それらを囲う結界の辺の長さを出力せよ。
もしも条件を満たす厄倖因子が一つも存在しない場合、
ヒナの力は覚醒することが出来ない。
それは、当然放送事故に他ならない。

入出力形式

一行目に、ヒナの持っている厄倖因子の数、因子の繋がりの数 N , M が一行に与えられる。
厄倖因子は、初めの入力から順に0,1,2と番号が割り振られている。
続いてN行に渡り、i番目の厄倖因子の座標 X , Y が空白区切りで与えられる。
続いてM行に渡り、何番目と何番目の厄倖因子が繋がっていることを示す A , B が空白区切りで与えられる。

N M
X₀ Y₀
X₁ Y₁
X₂ Y₂
..
..
X_N-1 Y_N-1
A₀ B₀
A₁ B₁
A₂ B₂
..
..
A_M-1 B_M-1

一行目に、ヒナのエネルギーになることができる厄倖因子の数の最大を出力し、
二行目に、ヒナのエネルギーになることができる厄倖因子を囲う為に必要な
結界の辺の数が最小になるときの、各辺の長さの合計を出力せよ。
なお、ヒナのエネルギーになることができる厄倖因子が一つも存在しない場合、
一行に "Broadcasting accident" と出力し終了せよ。

制約

入力される値は全て整数である。
1 ≦ N ≦ 10,000
0 ≦ M ≦ 100,000
0 ≦ X,Y ≦ 100,000,000
0 ≦ A,B ＜ N
厄倖因子は全て異なる座標に存在する。

入出力例

入力例一

出力例一

4
5.65685

この入力例では、厄倖因子は四つあり、全て同一の集合体に属している。
この四つある厄倖因子は、厄同士、福同士で繋がりが生まれないように状態を決めることが可能である。
その為、一行目には 4 を出力する。
これらの厄倖因子を結界で囲うためには、
0 -> 1 、 1 -> 2 、 2 -> 3 、 3 -> 0 の
合計四つの辺を張る必要がある。
この四つの辺の長さの合計を出力するので、
二行目には5.65685が出力されている。

入力例二

出力例二

4
11.8126

この入力例では、厄倖因子は七つあり、0~3と4~6が同一の集合体に属している。
4~6の集合体は、どのように状態を決めても、厄同士、もしくは福同士で繋がりが生まれてしまう。
このため、この三つの厄倖因子は条件を満たさず、結界で囲う必要がないことに注意せよ。

入力例三

1 0
1 1

出力例三

1
0

結界に辺はできない。
その為、辺の長さの合計は0となることに注意せよ。

入力例四

出力例四

2
1.41421

この例では、結界が直線になる。

入力例五

出力例五

Broadcasting accident

0763 - 魔女っ娘ヒナくるん -Magic.03