시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 10 4 4 57.143%

문제

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

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

입력

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

출력

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

예제 입력

8 5
1 2
6 1
7 6
8 6
1 3
5 3
4 3

예제 출력

1

힌트