E. DFS - Tìm kiếm theo chiều sâu

Bộ nhớ: 256 MiB Thời gian: 1000 ms Nhập/xuất từ luồng chuẩn
Kiểu bài: Thông thường Kiểu chấm: Trình chấm ngoài

Đề bài

Cho đồ thị vô hướng n đỉnh đánh số từ 1 đến n , m cạnh và hai đỉnh s , t .

Hãy tìm một đường đi từ đỉnh s tới đỉnh t .

Dữ liệu:

  • Dòng đầu chứa bốn số nguyên dương n, m, s, t\ (1\le n \le 1000, 1\le m \le 10^5, 1 \le s, t \le n, s \ne t) ;
  • m dòng sau, mỗi dòng chứa một cặp số nguyên u, v cho biết có một cạnh nối hai đỉnh u, v của đồ thị (1 \le u, v \le n, u \ne v) .

Kết quả:

  • Nếu không có đường đi đơn từ s đến t , ghi ra -1 , ngược lại, ghi kết quả theo định dạng:
    • Dòng đầu ghi số nguyên dương p là độ dài đường đi (số cạnh đi qua);
    • Dòng sau ghi danh sách các đỉnh trên đường đi (xuất phát từ s , kết thúc tại t ), nếu có nhiều đường đi thì ghi ra đường đi bất kỳ.

Ví dụ:

Dữ liệu:

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

Kết quả:

3
1 6 5 2