Cuối cùng cũng bị dồn vào đường cùng, Bessie đã lẩn trốn trong một trang trại hẻo lánh. Trang trại gồm \(N\) chuồng bò (\(2 \leq N \leq 10^5\)) và \(N-1\) đường hầm hai chiều nối các chuồng, sao cho giữa mọi cặp chuồng đều có một đường đi duy nhất. Mỗi chuồng có đúng một đường hầm nối với nó đều là một lối thoát. Khi trời sáng, Bessie sẽ xuất hiện tại một chuồng nào đó và cố gắng đi đến một lối thoát.

Nhưng ngay khi Bessie xuất hiện, lực lượng hành pháp sẽ có thể xác định chính xác vị trí của cô. Khi đó, một số nông dân sẽ bắt đầu từ các chuồng là lối thoát và cố gắng bắt Bessie. Những người nông dân di chuyển với cùng tốc độ như Bessie (vì vậy trong mỗi bước thời gian, mỗi nông dân có thể đi từ một chuồng sang một chuồng kề nó). Những người nông dân luôn biết Bessie ở đâu, và Bessie cũng luôn biết họ ở đâu. Những người nông dân bắt được Bessie nếu tại bất kỳ thời điểm nào có một nông dân ở cùng chuồng với Bessie hoặc đang đi qua cùng một đường hầm với Bessie. Ngược lại, Bessie trốn thoát nếu cô đến được một chuồng là lối thoát trước khi bất kỳ nông dân nào bắt được cô.

Bessie không chắc về cơ hội thành công của mình, bởi điều đó phụ thuộc vào số nông dân mà lực lượng hành pháp có thể điều động. Biết Bessie xuất hiện tại chuồng \(K\), hãy giúp cô xác định số nông dân ít nhất cần có để bắt được cô, giả sử những người nông dân phân bố tối ưu giữa các chuồng là lối thoát.

Dữ liệu vào

Dòng đầu tiên chứa \(N\) và \(K\). Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên, mỗi số thuộc khoảng \(1 \ldots N\), mô tả một đường hầm nối hai chuồng.

Dữ liệu ra

In ra số nông dân ít nhất cần có để đảm bảo bắt được Bessie.

Ví dụ

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

3

Nguồn

USACO 2018 January Contest, Gold — Cow at Large

Tác giả bài toán: Dhruv Rohatgi.