~H~ là một cô gái rất xinh đẹp, trong một buổi tiệc rất nhiều chàng trai muốn nhảy với ~H~, danh sách chàng trai được đánh số từ 1 đến ~N~. Cho biết danh sách những đôi được nhảy với nhau, bạn hãy xác định độ may mắn của các chàng trai. Biết rằng độ may mắn được tính dựa vào việc chàng trai có được trực tiếp nhảy với H hay không? Nếu nhảy trực tiếp độ may mắn là 1, nếu không được nhảy trực tiếp nhưng lại nhảy với người được nhảy với H sẽ có độ may mắn là 2, tương tự như vậy với các độ may mắn khác. Nếu chàng trai không được nhảy với ~H~ cũng như tập những người may mắn được nhảy với H sẽ xem như không may mắn và nhận giá trị -1.

Lưu ý: ~H~ được đánh số là 0

Input:

• Dòng đầu tiên chứa 2 số nguyên ~N~ và ~M~ tương ứng là số người trong bữa tiệc và số lượng đôi nhảy với nhau.

• M dòng tiếp theo, mỗi dòng là hai giá trị ~x~,~y~ tương ứng là hai người ~x~,~y~ đã nhảy với nhau.

Output:

• Ghi ra N-1 dòng, tại dòng thứ i là độ may mắn của người thứ i.

Ràng buộc:

• N<=1000 • ~M <=(N*(N-1))/2~

Ví dụ:

Input:

5 6 
0 1 
0 2 
3 2 
2 4 
4 3 
1 2

Output:

1 
1 
2 
2