정원 정리

정원을 정리하던 상욱은 몹시 어지럽게 자란 정원수 한 그루를 발견했다. 이제 가지치기를 할 때가 되었다.

정원수는 n개의 정점과 n - 1개의 간선으로 이루어진 연결 그래프로 표현된다. 각 정점은 정원수의 잎사귀, 각 간선은 가지라고 생각하자.

상욱은 가지치기를 해서 정원수에 남는 정점의 수가 정확히 m개가 되도록 만들고 싶다. 가지치기 한 번은 현재 남아 있는 정원수의 간선 하나를 끊는 작업이다. 간선을 끊어 그래프가 두 연결 성분으로 나뉘면, 그중 한쪽만 남기고 다른 한쪽은 버린다.

정원수의 모양이 주어졌을 때, 원하는 크기로 만들기 위해 필요한 가지치기 횟수의 최솟값을 구하시오.

첫째 줄에 n과 m이 주어진다. (1 <= n <= 150, 1 <= m <= n)

이후 n - 1개의 줄에는 정원수의 가지를 나타내는 두 정점 번호가 한 줄에 하나씩 주어진다. 두 번호는 그 정점들을 연결하는 간선이 있음을 의미한다. 정점 번호는 1 이상 n 이하의 정수이다.

가지치기 횟수의 최솟값을 출력한다. 불가능한 경우에는 -1을 출력한다.

공개 테스트에서는 간선 1-4와 1-5를 끊으면 원하는 크기의 정원수를 얻을 수 있다.