Cho một mạng lưới giao thông gồm N trạm kiểm lâm (được đánh số từ 1 đến N) và M tuyến đường hai chiều nối giữa các trạm. Hãy viết chương trình mô phỏng lại hành trình tuần tra của một nhân viên kiểm lâm bằng thuật toán Tìm kiếm theo chiều sâu (Depth First Search - DFS).

Quá trình tuần tra phải tuân thủ các quy định sau:

Hành trình luôn bắt đầu tại trạm số 1.

Khi đứng tại một trạm, nếu có nhiều trạm kề cạnh chưa được thăm, người kiểm lâm sẽ ưu tiên đi đến trạm xuất hiện trước trong danh sách dữ liệu đầu vào.

Mỗi trạm kiểm lâm chỉ được ghé thăm và ghi nhận vết chân đúng một lần.

📥 Dữ liệu vào (Input)

Dòng đầu tiên chứa hai số nguyên dương N và M (1≤N≤1000, 1≤M≤100000) lần lượt biểu diễn số lượng trạm kiểm lâm và số lượng tuyến đường.

Trong M dòng tiếp theo, mỗi dòng chứa hai số nguyên dương u và v (1≤u,v≤N) thể hiện có một tuyến đường hai chiều kết nối trực tiếp trạm u và trạm v.

📤 Dữ liệu ra (Output)

In ra một dòng duy nhất chứa dãy các trạm kiểm lâm theo đúng thứ tự đã được ghé thăm trong quá trình tuần tra. Các trạm phải được phân tách nhau bởi một khoảng trắng.

📊 Ví dụ (Sample)

Input:

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

Output:

1 2 3 5 4 6 7 8 9