Đánh Giá Nút Mạng
Hệ thống mạng viễn thông bao gồm nhiều máy chủ được kết nối với nhau bằng các tuyến cáp quang hai chiều. Trung tâm điều hành mạng nằm bên ngoài hệ thống và không đặt tại bất kỳ máy chủ nào. Để gửi thông điệp tới các máy chủ, trung tâm điều hành trước tiên phải sử dụng một trạm phát sóng vệ tinh dự phòng để truyền thông điệp tới một máy chủ trong mạng, sau đó thông điệp sẽ tự động được chuyển tiếp đến tất cả các máy chủ cùng thành phần liên thông thông qua các tuyến cáp quang. Mỗi trạm phát sóng vệ tinh chỉ có thể gửi thông điệp tới đúng một máy chủ.
Để đánh giá mức độ rủi ro khi một máy chủ bị sự cố, quản trị viên muốn tính toán chỉ số gián đoạn của từng máy chủ. Chỉ số gián đoạn của máy chủ $v$ là số lượng trạm phát sóng vệ tinh tối thiểu mà trung tâm điều hành cần sử dụng để có thể truyền thông điệp tới tất cả các máy chủ còn hoạt động sau khi loại bỏ máy chủ $v$ khỏi hệ thống mạng.
Nhiệm vụ của bạn là xác định $m$ máy chủ có chỉ số gián đoạn lớn nhất khi bị vô hiệu hóa.
Dữ liệu vào
Dữ liệu đầu vào gồm nhiều bộ thử nghiệm.
Mỗi bộ thử nghiệm bắt đầu bằng một dòng chứa hai số nguyên $n$ ($3 ≤ n ≤ 10000$) và $m$ ($1 ≤ m ≤ n$), trong đó $n$ là số lượng máy chủ trong hệ thống (được đánh số từ $0$ đến $n - 1$), và $m$ là số lượng máy chủ cần chọn ra có chỉ số gián đoạn lớn nhất. Ban đầu, mỗi máy chủ kết nối trực tiếp với tối đa 10 máy chủ khác và toàn bộ mạng tạo thành một đồ thị liên thông.
Các dòng tiếp theo mô tả các tuyến cáp quang. Mỗi dòng chứa một cặp số nguyên $x$ và $y$ ($0 ≤ x, y ≤ n - 1$) biểu thị tuyến cáp quang hai chiều nối trực tiếp giữa máy chủ $x$ và máy chủ $y$. Danh sách các tuyến cáp quang của một bộ thử nghiệm được kết thúc bằng dòng chứa hai số -1 -1.
Dữ liệu đầu vào được kết thúc bằng một dòng chứa hai số 0 0 ($n = 0, m = 0$). Bộ thử nghiệm này không được xử lý.
Kết quả
Với mỗi bộ thử nghiệm, in ra đúng $m$ dòng tương ứng với $m$ máy chủ có chỉ số gián đoạn lớn nhất. Mỗi dòng chứa hai số nguyên cách nhau bởi một khoảng trắng: số hiệu của máy chủ và chỉ số gián đoạn của máy chủ đó.
Danh sách các máy chủ được sắp xếp giảm dần theo chỉ số gián đoạn. Nếu có nhiều máy chủ có cùng chỉ số gián đoạn, sắp xếp tăng dần theo số hiệu máy chủ.
Sau khi in xong kết quả của mỗi bộ thử nghiệm, in thêm một dòng trống.
Chấm điểm
Subtask 1 (30 points). $n ≤ 1000$
Subtask 2 (30 points). $n ≤ 2000$
Subtask 3 (40 points). $3 ≤ n ≤ 10000$; $1 ≤ m ≤ n$
Ví dụ
Input
4 2
0 1
1 2
2 3
-1 -1
0 0
Output
1 2
2 2
Ghi chú
Chỉ số gián đoạn đại diện cho số lượng thành phần liên thông còn lại của đồ thị sau khi loại bỏ một đỉnh cụ thể. Đỉnh có chỉ số gián đoạn càng cao thì việc loại bỏ đỉnh đó càng làm phân mảnh mạng viễn thông.