트리 자르기
면접 대비시간 제한2초메모리 제한128 MB
n개의 정점으로 이루어진 트리에서 정점이 정확히 m개인 부분 트리가 나오도록 자를 최소 간선 수를 구하거나 불가능하면 -1을 출력합니다.
문제
트리는 사이클이 없는 연결 그래프이다. 트리에서 간선 하나를 자르면 두 개의 트리로 나뉜다.
정점이 n개인 트리가 주어진다. 간선을 몇 개 잘라서, 남은 연결 요소 중 정점이 정확히 m개인 트리가 하나 생기도록 하려 한다. 잘라야 하는 간선 수의 최솟값을 구하시오.
입력
첫째 줄에 n(1 ≤ n ≤ 150), m(1 ≤ m ≤ n)이 주어진다. 다음 n-1개의 줄에는 트리의 각 간선을 나타내는 두 정수 A, B가 주어진다. 이는 A번 정점과 B번 정점이 연결되어 있다는 뜻이다.
출력
첫째 줄에 정점이 m개인 트리를 얻기 위해 잘라야 하는 간선 수의 최솟값을 출력한다. 만들 수 없다면 -1을 출력한다.