KSA에서 숨바꼭질

면접 대비

시간 제한1.5초메모리 제한1024 MB

요약

트리가 주어질 때, 숨은 정점까지의 거리를 돌려주는 질의를 정보를 활용해 반복해서 던질 때, 숨은 정점을 알아내는 데 필요한 최소 질의 수를 구한다.

난이도: 보통10점 중 5점
유형: 트리, BFS, 구현
정답자: 아직 제출이 없습니다

문제

KSA에는 $1$ 번부터 $N$ 번까지의 건물이 있고 두 건물 사이를 양방향으로 연결하는 $N-1$ 개의 통로가 있다. $i$ 번 통로는 $A\_i$ 번 건물과 $B\_i$ 번 건물을 연결하며 임의의 건물에서 다른 건물로 가는 경로가 항상 존재한다. 민찬이와 에릭은 여기서 숨바꼭질하고 있다. 민찬이가 술래고 $1$ 번부터 $N$ 번 건물 중 어딘가에 숨은 에릭을 찾아야 한다.

민찬이는 남몰래 에릭의 옷에 숨겨놓았던 위치 추적 장치의 도움을 받아 숨바꼭질에서 이기려고 한다. 이 위치 추적 장치는 다음과 같은 방법으로만 위치를 알려준다.

위치 추적 장치의 리모컨에 정수 $x$ $(1 \leq x \leq N)$ 를 입력하면 $x$ 번 건물에서부터 에릭이 숨어있는 건물까지 가기 위해 지나야 할 최소 통로 수를 화면에 띄워준다.

위치 추적 장치의 배터리가 얼마 남지 않았기 때문에 민찬이는 위치 추적 장치를 많이 사용할 수 없다. 다음 행동을 $k$ 번 해서 에릭이 숨어있는 건물을 알 수 있는 가장 작은 $k$ 를 구해보자.

어떤 수 $x$ $(1 \leq x \leq N)$ 를 선택해서 리모컨에 입력한 후, 리모컨에 띄워지는 수를 확인한다.

단, 민찬이는 다음 행동을 결정할 때, 그 전 행동들에서 얻은 정보를 사용할 수 있다.

입력

첫 번째 줄에 정수 $N$ 이 주어진다.

$i+1$ 번째 줄에 두 정수 $A\_i$ 와 $B\_i$ 가 공백으로 구분되어 주어진다. $(1 \leq i \leq N-1)$

출력

에릭이 숨어있는 건물을 알기 위한 최소의 $k$ 를 출력한다.

제한

$2 \leq N \leq 2000$
$1 \leq A\_i < B\_i \leq N$ $(1 \leq i \leq N-1)$
$1 \leq i < j \leq N$ 인 모든 $i$ , $j$ 에 대해서 $i$ 번 건물과 $j$ 번 건물을 연결하는 경로가 존재

예제3

예제 1
입력
```
3
1 2
1 3
```
예상 출력
```
1
```
예제 2
입력
```
5
1 2
2 3
3 4
3 5
```
예상 출력
```
2
```
예제 3
입력
```
8
1 2
1 3
2 4
2 5
2 6
3 7
3 8
```
예상 출력
```
3
```