Cho đồ thị có hướng G = (V, E) được biểu diễn dưới dạng danh sách cạnh. Hãy thực hiện duyệt danh sách các đỉnh theo thuật toán DFS.

Đầu vào: Dòng đầu tiên là 2 số n và m và s, tương ứng với số lượng đỉnh, cạnh của đồ thị và đầu duyệt. Các đỉnh của đồ thị được đánh số từ 1 tới n; m dòng tiếp theo mỗi dòn đỉnh u, v (u!= v) tương ứng với một cạnh của đồ thị.

Ràng buộc: 1<=5<=n<=1000; 1<=m<=n*(n-1)/2;

Đầu ra: In ra các đỉnh được duyệt theo thuật toán DFS. Chú ý trong quá trình mở rộng các đỉnh của thuật toán DFS luôn lựa chọn duyệt các đỉnh có thứ tự nhỏ hơn trước.

Input:

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

Output:

4 2 3 1 5