F. BFS - Tìm kiếm theo chiều rộng

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ị có hướng n đỉnh đánh số từ 1 đến n , m cung và hai đỉnh s , t . Hãy tìm một đường đi ngắn nhất (đi qua ít cạnh nhất) 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 cung nối từ u đến 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 d là độ dài đường đi ngắn nhất (số cạnh đi qua);
    • Dòng sau ghi dãy đỉ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 (ngắn nhất) thì ghi ra đường đi ngắn nhất 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ả:

1
1 2