Submit solution
Points:
100.00 (partial)
Time limit:
1.0s
Memory limit:
1G
Input:
stdin
Output:
stdout
Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text
Đồ 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. Jame đang ở đỉnh ~S~, Alisa đang ở đỉnh ~T~. Họ hẹn gặp vào cuối tuần ở ~S~ hoặc ~T~. Hãy cho biết hành trình di chuyển của Jame hoặc Alisa để họ có thể gặp nhau tại ~S~ hoặc ~T~.
Dữ liệu vào gồm:
- Dòng 1: Ghi số nguyên dương ~N, M, S, T~ ~(M, N ≤ 3000, S, T ≤ N, S≠T)~.
- ~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~ tới ~T~ và ngược lại. 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 Jame và Alisa không có đường đi để gặp nhau tại ~S~ hoặc ~T~ thì ghi ra ~-1~.
![](http://oj.lequydon.net/media/martor/dc75a6bc-8fb7-4d2a-8e31-3844cc95804d.png)
Ví dụ:
INPUT
6 11 1 6
1 3
1 2
1 5
5 1
2 6
6 2
3 2
2 4
4 2
4 6
4 5
OUTPUT
6 4 2 1
6 2 1
1 5 4 2 6
(Truy vết ngược)
Comments