Mạng lưới đường phố của Bytown bao gồm $n$ nút giao thông và $n-1$ con đường hai chiều, mỗi con đường nối trực tiếp một cặp nút giao thông, và bất kỳ hai nút giao thông nào cũng có thể đi đến được với nhau. Để cải thiện giao thông, thị trưởng Byteasar muốn xây dựng một hệ thống tàu điện ngầm. Cụ thể, ông muốn đặt các ga tàu điện ngầm tại một số nút giao thông và trải đường ray dọc theo một số con đường. Mạng lưới tàu điện ngầm phải liên thông, nghĩa là tàu phải có khả năng di chuyển giữa bất kỳ hai ga tàu điện ngầm nào, có thể đi qua các ga khác trên đường đi.

Chi phí đào đường hầm rất cao, nhưng chi phí xây dựng các ga cuối (tức là các ga chỉ có một đường hầm dẫn đến) còn cao hơn, vì những ga này cần cơ sở hạ tầng bổ sung để đỗ và bảo trì tàu. Do hạn chế về tài chính, số lượng ga cuối tối đa chỉ có thể là $k$. Mặt khác, một mạng lưới tàu điện ngầm hợp lý cần ít nhất hai ga như vậy.

"Chỉ số khó chịu" của hành khách được định nghĩa là số lượng con đường ít nhất mà họ phải đi bộ từ nhà mình đến ga tàu điện ngầm gần nhất. Thị trưởng yêu cầu thiết kế một mạng lưới tàu điện ngầm sao cho giá trị lớn nhất của chỉ số khó chịu của tất cả hành khách là nhỏ nhất. Chúng ta giả định rằng tại mỗi nút giao thông đều có một số hành khách sinh sống.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($n \ge 3, 2 \le k \le n$), cách nhau bởi dấu cách, lần lượt là số lượng nút giao thông và số lượng ga cuối tối đa. Các nút giao thông được đánh số từ $1$ đến $n$.

$n-1$ dòng tiếp theo, mỗi dòng chứa hai số nguyên $a$ và $b$ ($1 \le a, b \le n, a \neq b$), cách nhau bởi dấu cách, biểu thị rằng nút giao thông $a$ và $b$ được nối trực tiếp bởi một con đường.

Dữ liệu ra

Dòng đầu tiên xuất ra hai số nguyên $r$ và $s$, cách nhau bởi dấu cách, lần lượt là giá trị nhỏ nhất của chỉ số khó chịu lớn nhất của hành khách, và số lượng ga cuối trong thiết kế đó (thỏa mãn $2 \le s \le k$). Dòng thứ hai xuất ra $s$ số nguyên phân biệt, nằm trong khoảng từ $1$ đến $n$, tương ứng với số hiệu của các nút giao thông được chọn làm ga cuối.

Trong tất cả các thiết kế mạng lưới, ưu tiên chọn thiết kế có $r$ nhỏ nhất. Nếu có sự cân bằng, mục tiêu phụ là tối thiểu hóa $s$. Nếu có nhiều thiết kế thỏa mãn $r$ nhỏ nhất và $s$ nhỏ nhất, bạn có thể xuất ra bất kỳ thiết kế nào trong số đó.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

1 2
8 1

Ghi chú

Mạng lưới đường phố được thể hiện như hình dưới đây. Thiết kế mạng lưới tàu điện ngầm tối ưu có hai ga cuối (nằm tại nút giao thông 1 và 8). Chỉ số khó chịu lớn nhất của hành khách tương ứng là 1. Lưu ý rằng vẫn tồn tại các thiết kế mạng lưới tàu điện ngầm tối ưu khác thỏa mãn $r=1$ và $s=2$. Ngoài ra cũng tồn tại các mạng lưới với $r=1$ và $s=3$, nhưng chúng không phải là tối ưu.

Ví dụ kiểm thử

• 1ocen: $n = 30, k = 29$, các nút giao thông $2, \dots, n$ đều được nối với nút giao thông $1$.
• 2ocen: $n = 5000, k = 4000$, các nút giao thông $1, 2, \dots, 2000$ nối tiếp nhau tạo thành một đường đi, các nút giao thông $2001, \dots, 3500$ đều được nối với nút giao thông $1$, các nút giao thông $3501, \dots, 5000$ đều được nối với nút giao thông $2000$.
• 3ocen: $n = 2^{20} - 1, k = 1509$, các nút giao thông tạo thành một cây nhị phân đầy đủ.

Nhiệm vụ con

Tập hợp các bài kiểm thử bao gồm các nhiệm vụ con sau đây. Mỗi nhiệm vụ con có thể chứa nhiều điểm kiểm thử. Nếu chương trình chỉ xuất ra đúng dòng đầu tiên, bạn sẽ nhận được 50% số điểm của điểm kiểm thử đó. Hãy nhớ rằng chương trình vẫn phải kết thúc bình thường và không được vượt quá giới hạn thời gian và bộ nhớ. Giới hạn thời gian cho mỗi nhiệm vụ con được đăng trên SIO.