Cho đồ thị vô hướng gồm \(n\) đỉnh và \(m\) cạnh, các đỉnh đánh chỉ số từ \(1\) đến \(n\). Tìm số cạnh ít nhất trên đường đi từ đỉnh \(1\) đến các đỉnh còn lại.

Input

• Dòng đầu ghi hai số nguyên dương \(n\) và \(m\) (\(1 \le n \le 1000\); \(1 \le m \le \min(10000, \frac{n(n-1)}{2})\)).
• Trong \(m\) dòng tiếp theo, mỗi dòng ghi \(2\) số nguyên \(x\) và \(y\) thể hiện một cạnh của đồ thị (\(1 \le x, y \le n\)).

Output

• Kết quả ghi ra gồm \(n - 1\) dòng, dòng thứ \(i\) ghi độ dài của đường đi ngắn nhất từ đỉnh \(1\) đến đỉnh \(i + 1\) (\(1 \le i \le n - 1\)). Nếu không có đường đi thì ghi \(-1\).

Example

5 4
1 2
2 3
1 3
2 5

1
1
-1
2