왕국 도로망

왕국은 n개의 도시로 이루어져 있으며, 이 도시들은 n − 1개의 도로로 연결되어 있습니다. 임의의 두 도시 사이에는 이동 경로가 정확히 하나만 존재합니다. 즉, 도시와 도로는 하나의 트리를 이룹니다.

왕은 매우 바빠서 도시들 사이를 끊임없이 오갑니다. 그런데 어느 날 이동 중에 도로 하나가 파손되어 큰 수리가 필요해졌고, 그 결과 왕은 제시간에 목적지에 도착하지 못했습니다.

이 일을 겪은 뒤 왕은 도로망의 신뢰성을 높이기로 했습니다. 새 도로망은 도로 하나가 파손되더라도 여전히 임의의 두 도시 사이를 오갈 수 있어야 합니다. 다시 말해, 어떤 도로 하나를 제거하더라도 모든 도시가 서로 연결된 상태를 유지해야 합니다. 예산이 한정되어 있으므로, 새로 건설하는 도로의 수는 최소로 해야 합니다.

어떤 도로 하나가 사용 불가능해지더라도 항상 임의의 두 도시 사이에 경로가 존재하도록 만들 때, 새로 건설해야 하는 도로의 최소 개수를 구하세요.

첫째 줄에 왕국의 도시 수 n이 주어집니다 (2 ≤ n ≤ 100 000).

다음 n − 1개의 줄에는 각각 두 정수 uᵢ, vᵢ가 주어지며, 이는 i번째 도로가 연결하는 두 도시를 의미합니다 (1 ≤ uᵢ, vᵢ ≤ n).

어떤 도로 하나가 사용 불가능해지더라도 모든 도시가 서로 연결된 상태를 유지하도록 만들기 위해 새로 건설해야 하는 도로의 최소 개수를 한 정수로 출력하세요.