디젤을 이겨라

화성의 동굴 계통을 탐사하는 일은 지구에서 미리 계획해 둔, 간단한 절차다. 각 동굴 계통에는 서로 연결되지 않은 여러 동굴 방이 있다. 동굴 방들은 지표에서 접근할 수 없으므로, 방 사이에 통로를 굴착할 수 있는 굴착기를 지급받았다.

토양은 균일하지 않고 굴착기를 돌리는 데는 디젤이 엄청나게 많이 든다. 디젤을 아끼려면, 모든 동굴에 지표에서 통로를 거쳐 접근할 수 있도록 최소 개수의 통로를 굴착해야 한다. 동시에, 지표에서 특정 동굴까지 가는 데 지나야 하는 통로의 수가 최소가 되도록 계통이 연결되어야 한다.

동굴 계통 전체를 스캔했고, 이제 각 동굴 방의 위험도를 알고 있다. 스캔 결과에는 어떤 동굴 방 쌍, 또는 어떤 동굴 방과 지표 사이의 토양을 파서 통로를 만들 수 있는지도 나온다. 동굴 방의 거리를, 가능한 모든 통로를 굴착했다고 할 때 지표에서 그 방까지 가는 데 지나야 하는 통로 수의 최솟값이라고 하자.

안전상의 이유로, 굴착 절차는 가까운(거리가 작은) 동굴 방을 더 먼 동굴 방보다 먼저 접근 가능하게 만들어야 한다고 규정한다. 이 규칙으로 다음에 접근 가능하게 만들 방이 유일하게 정해지지 않으면, 후보 중에서 가장 안전한(위험도가 낮은) 방을 고른다. 그래도 굴착해야 할 통로가 유일하게 정해지지 않으면, 이미 접근 가능한 출발 지점 중에서 가장 안전한 것을 고른다.

주어진 순서대로 방을 발견하다 보면 이미 굴착한 통로를 여러 번 지나야 한다. 굴착기를 옮기는 데 쓰는 기계도 디젤을 마시지만, 굴착기보다는 훨씬 적게 마신다. 이 작업을 하는 데 필요한 디젤의 양, 즉 0에서 시작해 모든 통로를 굴착할 때까지 지나야 하는 통로의 수가 궁금하다.

첫 번째 줄에는 두 정수 N과 M(1 ≤ N ≤ 2 · 105, 0 ≤ M ≤ 2 · 105)이 주어진다. 각각 동굴 방의 수(지표 포함)와 가능한 동굴 통로의 수다. 지표는 0으로 표시하고, 동굴 방은 1부터 N − 1까지의 정수로 표시하며 위험도가 커지는 순서로 번호가 매겨져 있다. 다음 M개의 줄에는 각각 두 정수가 주어지며, 이는 서로 연결하는 통로를 만들 수 있을 만큼 토양이 부드러운 두 동굴 방, 또는 동굴 방과 지표를 나타낸다.

주어진 절차에 따라 동굴 계통 전체를 접근 가능하게 만드는 데 필요한 총 통로 통과 횟수를 정수 하나로 출력한다.