Cho đồ thị vô hướng gồm ~ n ~ đỉnh và ~ m ~ cạnh, các đỉnh được đánh số thứ tự từ 1 đến ~ n ~ độ dài của mỗi cạnh bằng 1. Tìm độ dài đường đi ngắn nhất từ đỉnh 1 đến cách đỉnh còn lại của đồ thị.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên dương ~ n ~ và ~ m ~ ~ (1≤n, m≤10^5) ~
• ~ m ~ dòng tiếp theo, mỗi dòng gồm 2 số nguyên dương ~ x ~ và ~ y ~, chỉ 1 cạnh nối giữa hai đỉnh ~ x ~ và ~ y ~

Kết quả

• In ra ~ n ~ dòng, dòng thứ ~ i ~ là độ dài đường đi ngắn nhất từ đỉnh 1 đến đỉnh ~ i ~, nếu không thể đi từ 1 đến ~ i ~, in ra ~ -1 ~

Ràng buộc

Ví dụ:

Input 1

5 4
1 2
2 3
2 4
3 4 

Output 1

0
1
2
2
-1