Một thành phố có \(N\) ngôi làng được đánh số \(1,2,\ldots,N\) và \(N-1\) con đường nối giữa các làng. Mỗi con đường nối đúng hai làng và có độ dài \(1\). Từ một làng bất kỳ, có thể đi đến mọi làng khác theo các con đường này.

Để bảo đảm an toàn cho người dân, mỗi ngày đội tuần tra của cảnh sát phải đi qua tất cả các con đường. Đồn cảnh sát nằm ở làng \(1\), nên đội tuần tra phải xuất phát từ làng \(1\) và cuối ngày quay lại làng \(1\).

Thành phố dự định xây thêm đúng \(K\) đường tắt để giảm tổng quãng đường tuần tra. Mỗi đường tắt có độ dài \(1\) và có thể nối hai làng bất kỳ. Hai đường tắt có thể chung đầu mút; một đường tắt thậm chí có thể nối một làng với chính nó.

Do kinh phí hạn chế, \(K\) chỉ có thể bằng \(1\) hoặc \(2\). Để bảo đảm các đường tắt được sử dụng, đội tuần tra bắt buộc phải đi qua mỗi đường tắt đúng một lần mỗi ngày. Các con đường ban đầu vẫn phải được đi qua ít nhất một lần.

Hãy xác định tổng quãng đường tuần tra nhỏ nhất có thể đạt được sau khi chọn vị trí xây \(K\) đường tắt.

Dữ liệu vào

Dòng đầu chứa hai số nguyên \(N,K\) với \(1\le K\le 2\).

Mỗi dòng trong \(N-1\) dòng tiếp theo chứa hai số nguyên \(A,B\) với \(1\le A,B\le N\), cho biết có một con đường nối làng \(A\) với làng \(B\).

Dữ liệu ra

In một dòng chứa một số nguyên: tổng quãng đường nhỏ nhất mà đội tuần tra phải đi mỗi ngày sau khi xây \(K\) đường tắt.

Ràng buộc

• \(3\le N\le 100\,000\).
• \(1\le K\le 2\).
• \(N-1\) con đường ban đầu nối tất cả các làng thành một mạng liên thông.

Phân nhóm

Mỗi phân nhóm được chấm độc lập theo kiểu tất cả hoặc không: bạn chỉ nhận điểm của nhóm khi đúng toàn bộ test trong nhóm. Điểm trong bảng là phần điểm cộng thêm trên LQDOJ; các nhóm có điều kiện bao hàm nhau sẽ dùng lại những test tương ứng.

Ví dụ

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

11

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

10

5 2
1 2
2 3
3 4
4 5

6

Nguồn

APIO 2010 — Patrol, đề tiếng Anh phiên bản 1.2.