광섬유망 정비 (Fiber)

크로아티아에서는 국내의 모든 도시를 광섬유망으로 연결하는 계획이 진행 중이다. 광섬유를 사용한 통신 회선은 품질이 매우 높고 속도가 빨라서, 여러 도시를 경유하더라도 속도가 거의 떨어지지 않고 고속 통신을 할 수 있다. 예를 들어 $k$개의 도시 $A_1, \dots, A_k$에 대해 도시 $A_i$와 $A_{i+1}$ ($1 \le i \le k-1$) 사이에 광섬유가敷設되어 있으면, 도시 $A_1$과 $A_k$ 사이에서 고속 통신을 할 수 있다.

크로아티아 정부는 국가 전체에 광섬유망을 펼쳐서 모든 도시와 도시 사이에서 고속 통신을 할 수 있게 하고 싶어 한다. 그런데 난처하게도, 현재는 규제 완화의 영향으로 여러 광섬유敷設業者가 난립해 있어서 국가 전체의 광섬유망이 어떻게 되어 있는지 아무도 파악하지 못하고 있다. 그래서 각 업자로부터 제출된 광섬유敷設情報를 바탕으로, 모든 도시와 도시 사이의 고속 통신을 가능하게 하려면 광섬유를 앞으로 몇 개 더 새로敷設해야 하는지 조사하기로 했다.

광섬유敷設情報가 주어졌을 때, 모든 도시와 도시 사이에서 고속 통신을 가능하게 하기 위해 앞으로 몇 개의 광섬유를 새로敷設해야 하는지 구하는 프로그램을 작성하라.

입력의 첫째 줄에는 크로아티아 국내의 도시 개수 $n$ ($1 \le n \le 10000$)이 적혀 있다. 각 도시에는 1부터 $n$까지의 번호가 붙어 있다. 둘째 줄에는敷設되어 있는 광섬유의 개수를 나타내는 정수 $m$ ($1 \le m \le 30000$)이 적혀 있다. 이어지는 $m$개의 줄(3번째 줄부터 $m+2$번째 줄까지)은 광섬유敷設情報를 나타낸다. $i+2$번째 줄 ($1 \le i \le m$)에는 2개의 서로 다른 정수 $a_i, b_i$ ($1 \le a_i, b_i \le n$, $a_i \ne b_i$)가 공백으로 구분되어 적혀 있다. 이는 도시 $a_i$와 도시 $b_i$ 사이에 광섬유가敷設되어 있음을 의미한다.

출력은 표준 출력으로 한다. 모든 도시와 도시 사이에서 고속 통신을 가능하게 하기 위해 새로敷設이 필요한 광섬유 개수의 최솟값을 출력하라. 만약 현재 상태로도 모든 도시와 도시 사이에서 고속 통신이 가능하다면 0을 출력하라.

이 입력 예에 대응하는 8개 도시 사이의 광섬유망을 그림으로 나타내면 다음과 같다.

광섬유를 2개 새로敷設하면 모든 도시와 도시 사이에서 고속 통신이 가능해진다. 예를 들어 도시 2와 1, 도시 6과 4 사이에敷設하면 된다. 이것이 새로 필요한 광섬유 개수의 최솟값이다.