Cho một đồ thị có hướng có \(N\) đỉnh và \(M\) cạnh. Sử dụng thuật toán BFS để tính và in ra khoảng cách (số cạnh) từ đỉnh nguồn \(S\) đến tất cả các đỉnh khác trong đồ thị.
Input
- Dòng đầu tiên là ba số nguyên dương \(N, M, S\) (\(1 \leq N \leq 10^5, 1 \leq M \leq 10^5, 1 \leq S \leq N\)).
- \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên \(u, v\) mô tả một cạnh.
Output
\(N\) dòng, dòng thứ \(i\) chứa khoảng cách từ đỉnh \(S\) đến đỉnh \(i\). Nếu không có đường đi, in ra -1.
Example
Test 1
Input
5 3 1
1 2
2 3
4 5Output
0
1
2
-1
-1
Bình luận
Đăng nhập để bình luận
Chưa có bình luận nào.