보물찾기

n개의 방으로 이루어진 미로가 있다. 어떤 두 방 사이에도 경로가 정확히 하나 존재한다.

한 방에는 보물이 숨겨져 있다. 탐색자는 질문할 때마다 특정 방 하나를 고른다. 그 방이 보물이 있는 방이면 정답이라는 답을 듣는다. 그렇지 않으면, 고른 방에 연결된 복도 중 어느 복도로 가야 보물이 있는 방에 가까워지는지 알려 준다.

미로의 구조가 주어졌을 때, 탐색자가 항상 최선의 방을 고른다고 하자. 보물의 위치가 최악인 경우에도 위치를 확정하기 위해 필요한 질문 수의 최솟값을 구하라.

첫째 줄에 방의 수 n이 주어진다. (1 ≤ n ≤ 50,000)

다음 n - 1개의 줄에는 두 정수 a, b가 주어진다. 이는 a번 방과 b번 방 사이를 오갈 수 있는 복도가 있다는 뜻이다. 방 번호는 1번부터 n번까지이다.

최선의 전략을 사용해도 최악의 경우에 필요한 질문 수를 출력한다.

보이는 테스트의 구조에서는 처음에 1번, 2번, 또는 3번 방을 물으면 두 번 이하의 질문으로 보물의 위치를 확정할 수 있다. 처음에 4번이나 5번 방을 물으면 최악의 경우 세 번의 질문이 필요하다.