Tại quần đảo ZXY có ~N~ hòn đảo, một số hòn đảo đã có cầu nối với nhau, không có chu trình. Từ đảo này ta có thể đi sang đảo khác bằng đường đi trực tiếp hoặc đi gián tiếp qua các đảo khác.

Jame vừa đến hòn đảo ~S~, anh muốn đi bằng đường bộ đến các đảo khác. Khi đến một đảo, anh ấy có thể nghỉ ngơi ở đảo ấy hoặc đi tiếp sang các đảo khác. Tất nhiên, anh ấy chỉ muốn tham quan mỗi đảo một lần. Do thời gian đi du lịch không nhiều, nên anh ấy muốn tham qua ~K~ đảo trong quần đảo ZXY.

Hãy tìm các hành trình mà Jame có thể tham quan bằng đường bộ theo yêu cầu trên.

Dữ liệu vào gồm:

• Dòng 1: Ghi số nguyên dương ~N, M, S~ và ~K~ ~(M, N ≤ 3000, K , S ≤ N)~.
• ~M~ dòng tiếp theo, mỗi dòng ghi số nguyên dương ~u~ và ~v~ thể hiện có đường đi giữa hai đỉnh ~u~ và ~v~ ~(u, v ≤ N)~.

Kết quả: Ghi ra các hành trình tham quan đi qua ~K~ hòn đảo. Mỗi số cách nhau một dấu cách. Nếu không có phương án tham quan, ghi ra ~-1~.

Ví dụ:

INPUT

12 7 1 3
1 2
2 5
2 6
6 10
3 4
9 11
9 12

OUTPUT

5 2 1
6 2 1

(truy vết ngược)