Cho đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh. Tìm đường đi ngắn nhất từ \(1\) đến các đỉnh từ \(2\) đến \(n\).

Input

• Dòng đầu tiên gồm \(2\) số nguyên \(n,m\).
• \(m\) dòng tiếp theo, mỗi dòng gồm \(2\) số nguyên \(u,v\), thể hiện có cạnh nối \(2\) đỉnh này.

Output

• In ra \(n-1\) số nguyên, số thứ \(i\) là độ dài đường đi ngắn nhất từ \(1\) đến \(i+1\). Nếu không có đường đi đến \(i+1\), in ra \(-1\).

Điều kiện

• \(1 \le n,m \le 10^5\)
• \(1 \le u,v \le n\)

Sample Input 1

5 4
1 2
1 3
2 3
4 5

Sample Output 1

1 1 -1 -1