원더랜드의 Bob

모두가 알다시피 사슬은 연결된 고리로 이루어진다. 일반적으로 모든 고리는 모양과 크기가 같다. Bob은 대장장이 견습생이고, 자신의 첫 이리듐 사슬을 만들고 있다. 그는 사슬 제작의 전통적인 공식을 따른다. 공식은 다음과 같다.

• 아직 사슬이 없으면 고리를 하나 만들고, 그것이 사슬의 한 조각이 된다.
• 사슬 조각이 있으면 고리를 하나 더 만들어, 이미 가지고 있는 사슬 조각의 다른 고리 하나에 연결한다.

Bob은 첫 번째 고리를 만들었다. 그다음에는 고리를 하나 더 만들 때마다 공식이 시키는 대로 자신의 사슬 조각에 있는 다른 고리 하나에 연결했다.

작업을 마치고 보니, 그가 만든 물체는 평범한 사슬과 전혀 닮지 않았다. 사슬을 펴려고 그는 사슬의 끝처럼 보이는 두 고리를 반복해서 골라 가능한 한 멀리 잡아당겼다. 그러나 펴진 부분에서 여러 위치에 "사슬"의 다른 조각들이 늘어져 있었다.

Bob에게는 자신의 작업이 아직 끝나지 않았다는 것이 분명했고, 그가 만든 물체를 미완성 사슬이라고 부르기로 했다. 더 고민한 끝에 Bob은 목표로 하는 곧은 사슬을 얻으려면 고리 몇 개를 부러뜨려 미완성 사슬의 나머지 부분에 더 조심스럽게 다시 연결해야 한다는 결론에 도달했다. 곧은 사슬에서는 각 고리가 많아야 두 개의 다른 고리와 연결되고, 곧은 사슬은 고리를 부러뜨리지 않고는 더 많은 조각으로 나눌 수 없다.

이제 더 조심스럽게, Bob은 간단한 단계로 진행하려고 한다. 한 단계에서 그는 미완성 사슬에서 다른 고리 B에 연결된 고리 A를 고른다. 그런 다음 A를 부러뜨려 B에서 분리하고, A를 미완성 사슬의 또 다른 고리 C에 다시 연결한다. 원래 A에 B 외에 다른 고리가 더 연결되어 있으면, Bob은 그 단계 내내 그 고리들을 A에 연결된 상태로 유지한다.

Bob이 곧은 사슬을 얻기 위해 수행해야 하는 최소 단계 수는 얼마인가?

첫째 줄에는 미완성 사슬의 고리 수를 나타내는 정수 N (1 ≤ N ≤ 3 · 10^5)이 주어진다. 고리에는 1, 2, ..., N이라는 번호가 붙어 있다. 다음 N − 1개 줄에는 미완성 사슬에서 연결된 두 고리의 번호가 주어진다. 연결은 임의의 순서로 나열된다. 미완성 사슬은 하나의 조각만 형성한다고 보장된다.

Bob의 미완성 사슬을 곧은 사슬로 바꾸는 최소 단계 수를 출력한다.

그림 1: Sample Input 1, Sample Input 2, Sample Input 3의 예시