から までの番号が付いた 人がいる。人 は人 と親しくなりたい。
異なる二人の間に友人関係を作ることができる。友人関係は双方向で、同じ二人の間には一つだけ作れる。二人 の間の親密度 を、友人関係をたどって人 から人 に到達するために必要な友人関係の最小数と定義する。 なら である。
ちょうど 個の友人関係を作り、全員が互いにつながるようにする。次の合計を最小化せよ。
最小値と、それを達成する友人関係を出力せよ。 の場合も許される。
入力は以下の形式で与えられる。
最初の行に親密度の合計の最小値を出力せよ。
続く 行に、友人関係を作る二人の番号 を空白区切りで出力せよ。各関係は , を満たさなければならない。同じ二人の関係を重複して出力してはならず、全員が連結でなければならない。
出力した関係での親密度の合計は、最初の行の最小値と一致しなければならない。解が複数ある場合はどれを出力してもよい。関係の順序と各関係の二人の番号の順序は自由である。
| 4 | 38 | 추가적인 제약이 없다. |