2337번 - 트리 자르기

트리는 사이클이 없는 연결된 그래프이다. 그렇기 때문에, 트리에서 임의의 한 간선을 자르면 두 개의 트리로 나뉘게 된다.

크기(트리의 정점의 개수)가 n인 트리의 간선을 자르는 과정을 반복하여, 크기가 m인 트리를 얻어내려 한다. 이때 잘라야 하는 간선의 최소 개수를 구해 내는 프로그램을 작성하시오.

첫째 줄에 n(1 ≤ n ≤ 150), m(1 ≤ m ≤ n)이 주어진다. 다음 n-1개의 줄에는 트리의 각 간선에 대한 정보를 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 의미이다.

첫째 줄에 잘라야 하는 간선의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.