농부 존은 소들을 운동시키는 끊임없는 일을 계속하고 있었다. 그 일은 소들을 목초지에 있는 다양한 소들의 길을 따라 달리게 하는 것이었다. 이 소들의 길은 꼭지점들의 집합과 양방향의 선분들로 표현되며, 각각의 선분은 두 개의 꼭지점을 연결하는 하나의 길이 된다. 이렇게 꼭지점들과 선분을 그리면 트리형태를 놀랍도록 닮을 것이다. 더 놀라운 것은 각각의 선분들은 모두 같은 길이를 가진다는 것이다.
주어진 소들의 길에 대해 약삭빠른 소들은 꼭지점 두 개 사이의 가장 긴 거리가 얼마인지 계산하고, 그것을 경로 길이라고 부른다. 만약 그들이 생각하기에 경로 길이가 너무 길면 그들은 운동하기를 완전히 거부할 것이다.
농부 존은 V (2<=V<=100000) 개의 꼭지점을 가진 지도를 그렸다. (각각의 꼭지점은 편의상 1 부터 V 까지 번호를 붙이자.) 그는 소들을 운동시켜야하기 때문에 더 짧은 경로 길이를 만들기 위해서 어떤 길이든 막아버릴 수 있다. (어떤 선분이든 제거할 수 있다.) 따라서 전체 선분들을 여러 개의 집합으로 나눔으로써 각각의 경로 길이를 감소시킬 수 있다.
초기 길의 상태에서 농부 존은 S (1<=S<=V-1) 개의 길을 막을 수 있으며 따라서 길의 상태를 S+1 개의 선분 집합으로 나눌 수 있다. 당신이 할 일은 농부 존이 막을 수 있는 길의 숫자가 주어질 때, 만들 수 있는 가장 짧은 경로 길이를 구하는 것이다.
처음에 농부 존은 V-1 개의 선분의 정보를 가지고 있으며 각각의 정보는 꼭지점 A_i 와 꼭지점 B_i 로 주어진다. (각 선분은 A_i 와 B_i 를 연결한다.)
다음의 예시를 보자. 처음에 7개의 꼭지점과 6개의 길이 다음과 같이 나있고, 농부 존은 2개의 길을 막을 수 있다고 하자.
1---2---3---4---5---6---7
그러면 다음과 같이 막아서 가장 긴 경로 길이를 2 로 만들 수 있다.
1---2 | 3---4 | 5---6---7
따라서 답은 2 가 될 것이다.
입력 7 2 6 7 3 4 6 5 1 2 3 2 4 5 출력 2
출처: USACO 2010 DEC gold 번역: KangJ