THỰC HÀNH

Cho đơn đồ thị vô hướng liên thông G(V, E) có n đỉnh và m cạnh. Hãy xây dựng cây khung của G.

Dữ liệu vào:

• Dòng đầu chứa hai số nguyên n và m là số đỉnh và số cạnh của G.
• m dòng tiếp theo, mỗi dòng chứa một cặp số u, v cho biết một cạnh nối hai đỉnh u và v trong G.

Dữ liệu ra:

Danh sách các cạnh của cây khung (n – 1 cạnh, mỗi cạnh trên một dòng).

Ví dụ:

Dữ liệu vào:
4 6
1 2
1 3
1 4
2 3
2 4
3 4
Dữ liệu ra:
1 2
1 3
1 4

Giới hạn: 1 ≤ n ≤ 10000; 0 ≤ m ≤ 500000 ≤ n(n – 1)/2.