Mạng tốc độ cao

Arkady đang xây dựng một mạng trao đổi Internet tốc độ cao. Mạng gồm $n$ nút được nối bởi số dây ít nhất có thể sao cho toàn bộ mạng liên thông (mỗi dây nối trực tiếp hai nút). Có đúng $k$ nút được chọn làm nút thoát: mỗi nút thoát phải có bậc đúng bằng $1$ (nối với đúng một nút khác); tất cả các nút còn lại phải có bậc ít nhất $2$ để tăng tính ổn định của hệ thống.

Vì mạng liên thông và có $n-1$ cạnh nên nó là một cây. Yêu cầu: hãy xây dựng cây sao cho khoảng cách lớn nhất giữa hai nút thoát bất kỳ là nhỏ nhất có thể. Khoảng cách giữa hai nút là số dây trên đường đi đơn nối chúng.

Dữ liệu vào

Một dòng duy nhất chứa hai số nguyên $n$ và $k$.

Dữ liệu ra

• Dòng đầu in một số nguyên — khoảng cách nhỏ nhất có thể giữa hai nút thoát xa nhau nhất.
• Trong $n-1$ dòng tiếp theo, mỗi dòng in hai số nguyên là chỉ số hai đầu của một dây. Các nút được đánh số từ $1$ đến $n$. Mỗi cạnh in đúng một lần, thứ tự cạnh và thứ tự hai đầu là tuỳ ý. Các nút thoát có thể có chỉ số bất kỳ.

Nếu có nhiều cách xây dựng tối ưu, in ra bất kỳ cách nào.

Ràng buộc

• $3\le n\le 2·{10}^5$
• $2\le k\le n-1$

Ví dụ