BFS01
Cho đồ thị vô hướng \(n\) đỉnh và \(m\) cạnh, các đỉnh được đánh số từ 1 đến \(n\).
Yêu cầu: Tính độ dài đường đi ngắn nhất từ đỉnh 1 đến các đỉnh còn lại.
Input
Dòng đầu chứa hai số nguyên dương \(n,m (1≤n≤10^3; 1≤m≤min(10^4,n*(n-1)/2).\)
\(m\) dòng tiếp theo, mỗi dòng chứa hai số \(u,v (1≤u,v≤n)\) thể hiện cạnh của đồ thị.
Output
- Gồm \(n-1\) dòng, dòng thứ \(i\) ghi độ dài đường đi từ đỉnh 1 đến đỉnh thứ \(i+1 (1≤i≤n-1)\). Nếu không có đường đi ghi \(-1.\)
Sample Input
5 4
1 2
2 3
1 3
2 5Sample Output
1
1
-1
2
Comments
skibidi