시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 66 27 25 54.348%

문제

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

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

입력

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

출력

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

예제 입력 1

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

예제 출력 1

1