Cho một đồ thị vô hướng, có thể có nhiều thành phần liên thông, được biểu diễn dưới dạng danh sách kề. Hãy viết chương trình duyệt đồ thị bằng thuật toán DFS (Depth-First Search) để tìm thứ tự các đỉnh được thăm khi bắt đầu từ một đỉnh cho trước. Yêu cầu bài toán

1. Dữ liệu vào:

• Dòng đầu tiên chứa hai số nguyên ~V~ ~(1 ≤ V ≤ 10^5)~ và ~E~ ~(0 ≤ E ≤ 2 × 10^5)~, lần lượt là số đỉnh và số cạnh của đồ thị.
• ~E~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u~ ~v~ ~(1 ≤ u, v ≤ V)~, thể hiện một cạnh nối giữa đỉnh u và đỉnh ~v~.
• Dòng cuối cùng chứa một số nguyên ~S~ ~(1 ≤ S ≤ V)~, là đỉnh xuất phát để bắt đầu duyệt DFS.

2. Dữ liệu ra:

• Một dòng duy nhất in ra thứ tự các đỉnh được duyệt bằng thuật toán DFS, bắt đầu từ đỉnh ~S~.
• Nếu có nhiều đỉnh có thể thăm từ một đỉnh, luôn chọn đỉnh có số nhỏ hơn trước để duyệt trước.

Ví dụ

Input 1:

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

Output 1:

1 2 4 3 5 6