시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 124 36 24 27.586%

문제

N(1≤N≤150)개의 원자로 구성된 분자가 있다. 각각의 원자들은 1부터 N까지의 번호가 붙어 있으며, 모든 원자들이 하나의 분자로 모두 연결되어 있다. 화학 실험을 할 때 결합 반응과 분해 반응에 대한 실험을 쉽게 하기 위해서, 원자들을 총 N-1 개의 결합만을 하고 있다.

실험을 하던 도중에 M개의 원자로 구성된 분자가 필요해졌다. 이 분자의 원자들의 종류는 상관이 없고, 단지 M개의 원자로 구성되어 있기만 하면 된다. 물론 이 역시 M개의 원자들이 하나의 분자로 모두 연결되어 있어야 한다. 이를 위해서, 주어진 분자의 몇 개의 결합을 해제하는 분해 반응을 거쳐야 한다.

한 번의 반응을 거치면 오직 한 개의 결합만이 해제된다. 이를 통해 하나의 분자를 두 개의 분자로 나눌 수 있다. 이제 이 두 개의 분자들 중 하나를 택해서 M개의 원자로 구성된 분자를 얻을 때까지 계속 분해 반응을 진행한다. 이러한 분해 반응을 진행하다 보면 물질의 안정성이 깨질 수도 있기 때문에, 당신은 최소 회수의 분해 반응을 이용하려 한다.

원자들의 연결 상태가 주어졌을 때, M개의 원자로 구성된 분자를 얻어내기 위한 최소 분해 반응 회수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 두 정수 N, M(1≤M≤N)이 주어진다. 다음 N-1개의 줄에는 원자들의 연결 상태를 나타내는 서로 다른 두 정수 A, B(1≤A, B≤N)가 주어진다. 이는 A번 원자와 B번 원자가 결합을 이루고 있다는 의미이다.

출력

첫째 줄에 답을 출력한다.

예제 입력

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

예제 출력

1

힌트

1번 원자와 3번 원자의 결합을 해제할 경우 1, 2, 6, 7, 8번 원자로 구성된 분자를 얻는다.