A. Mạng sao (STARNET)

Bạn được cho một đơn đồ thị vô hướng, không có khuyên, không trọng số, liên thông gồm đỉnh và cạnh.

Nhiệm vụ của bạn là tìm bất kỳ cây khung nào của đồ thị này sao cho bậc lớn nhất trên tất cả các đỉnh là lớn nhất có thể. Nhắc lại rằng, bậc của một đỉnh là số cạnh kề với nó.

Dữ liệu:

• Dòng đầu tiên chứa hai số nguyên và (, ) — lần lượt là số đỉnh và số cạnh.
• dòng tiếp theo mô tả các cạnh: cạnh thứ được biểu diễn bởi một cặp số nguyên , (, ).

Kết quả:

• In ra dòng mô tả các cạnh của một cây khung sao cho bậc lớn nhất trên tất cả các đỉnh là lớn nhất có thể. Đảm bảo rằng các cạnh của cây khung được in ra tạo thành một tập con của các cạnh đầu vào (thứ tự không quan trọng và cạnh được coi là giống như cạnh ).
• Nếu có nhiều câu trả lời khả thi, hãy in ra bất kỳ câu trả lời nào.

Ví dụ:

Dữ liệu:

5 5
1 2
2 3
3 5
4 3
1 5

Kết quả:

3 5
2 1
3 2
3 4

Dữ liệu:

4 6
1 2
1 3
1 4
2 3
2 4
3 4

Kết quả:

4 1
1 2
1 3

Dữ liệu:

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

Kết quả:

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

Giới hạn:

• Subtask #1 (20% số điểm): .
• Subtask #2 (30% số điểm): .
• Subtask #3 (10% số điểm): .
• Subtask #4 (40% số điểm): .