분자 분해 반응

원자 N개로 이루어진 하나의 분자가 있다. 원자는 1번부터 N번까지 번호가 붙어 있다. 분자 안의 결합은 정확히 N-1개이며, 모든 원자가 결합을 따라 서로 이어져 있으므로 결합 구조는 트리이다.

실험 중 원자 M개로 이루어진 분자가 필요해졌다. 어떤 원자를 골라도 상관없지만, 선택된 M개의 원자는 결합을 통해 하나의 분자로 연결되어 있어야 한다.

한 번의 분해 반응은 결합 하나를 끊어 현재 분자 하나를 두 분자로 나눈다. 나뉜 두 분자 중 하나를 계속 선택하여 다시 분해할 수 있다. 원자 M개로 이루어진 분자를 얻을 때까지 필요한 분해 반응 횟수를 최소화해야 한다.

원자의 결합 상태가 주어질 때, 원자 M개로 이루어진 분자를 얻기 위해 필요한 최소 분해 반응 횟수를 구하시오.

첫째 줄에 두 정수 N, M (1 ≤ M ≤ N ≤ 150)이 주어진다.

다음 N-1개의 줄에는 결합을 이루는 서로 다른 두 원자 A, B (1 ≤ A, B ≤ N)가 주어진다. 이는 A번 원자와 B번 원자가 직접 결합되어 있다는 뜻이다.

첫째 줄에 필요한 최소 분해 반응 횟수를 출력한다.

1번 원자와 3번 원자 사이의 결합을 끊으면 1, 2, 6, 7, 8번 원자로 이루어진 분자를 얻을 수 있다.