Đồ thị có hướng là đồ thị mà tất cả các cạnh trong đồ thị có hướng. Cạnh (u, v) thể hiện chỉ có đường đi từ đỉnh u tới đỉnh v. Cho đồ thị có hướng có N đỉnh, M cạnh. Hãy liệt kê các đường đi xuất phát từ đỉnh S.

Dữ liệu:

• Dòng 1: Ghi số nguyên dương N, M và S (M, N ≤ 3000, 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 từ đỉnh u đến đỉnh v (u, v ≤ N).

Kết quả: Ghi ra các đường đi xuất phát từ đỉnh S. Mỗi đường đi trên một hàng. Mỗi số ghi cách nhau một dấu cách. Nếu từ S không có đường đi sang đỉnh khác thì ghi ra -1.

Ví dụ:

input:

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

output:

1 2
5 1 2
10 1 2
6 10 1 2
(Truy vết ngược)