D - Power Grid

ある街に新しく発電所を作ることになりました。
新しい発電所は非常に大きな出力を持っており、いままで街の中にあったいくつかの小さな発電所の出力をすべてまかなえることがわかったので、古い発電所をすべて廃止することになりました。

しかし、もともと小さな発電所で電気をやりくりしていた関係で、ある電柱と別のある電柱の間では送電線がつながっていない可能性があることがわかりました。
調査の結果、街には現在本の電柱と本の送電線があり、番目の送電線は電柱を相互につないでいることがわかっています。

新たな発電所から電柱1にのみ送電線が引かれるとしたとき、最小で何本の新たな送電線を引くことですべての電柱に電気を行き渡らせることができますか?

• 入力はすべて整数

入力サイズが大きい可能性があるので、より高速な入出力を行うことを推奨します

入力は以下の形式で与えられる

5 3
1 2
1 3
1 4

1

電柱は全てで{1, 2, 3, 4, 5}の5本あります。 電柱1は電柱2, 3, 4と相互に接続されています。しかし、電柱5はどこにも接続されていないので例えば電柱4から5への送電線を新たに新設することで目標を達成できます。

3 2
1 2
2 3

0

どうやら最初からすべての電柱が接続されていたようです。

9 0

8

例えばすべての電柱を直列に接続するなどしなければいけません。