Mạng lưới thành phố của một quốc gia gồm \(n\) thành phố, các thành phố được đánh số thứ tự từ \(1\) đến \(n\). Các thành phố này được kết nối với nhau bởi \(m\) con đường cao tốc hai chiều, con đường thứ \(i\) nối liền hai thành phố \(u_i\) và \(v_i\). Hệ thống các con đường cao tốc được thiết kế sao cho từ bất kỳ thành phố nào đều có thể đi đến tất cả thành phố khác bằng cách đi qua một hoặc một số đường cao tốc nhất định.

Mức độ quan trọng của một thành phố được xác định bằng số lượng khu vực riêng biệt mà quốc gia sẽ bị chia cắt nếu ta đóng cửa thành phố này cùng với tất cả các đường cao tốc kết nối với thành phố đó.

Yêu cầu

• Hãy lập trình xác định mức độ quan trọng của các thành phố.

Dữ liệu vào

• Dòng đầu ghi hai số nguyên dương \(n\) và \(m\)
• Dòng thứ \(i\) trong \(m\) dòng tiếp theo ghi hai số nguyên dương \(u_i\) và \(v_i\) \((1 \le u_i,v_i \le n)\)
• Dữ liệu cho luôn đảm bảo giữa hai thành phố luôn có cách đi qua lại
• Giữa hai thành phố có tối đa một đường cao tốc nối trực tiếp.

Dữ liệu ra

• \(N\) số, số thứ \(i\) cho biết mức độ quan trọng của thành phố thứ \(i\).

Ràng buộc

• 40% số điểm có \(2 \le n \le 100\) và \(m \le 10^3\)
• 60% số điểm có \(10^3 \le n \le 10^5\) và \(m \le 2 \times 10^5\)

Input 1

7 7
1 2
2 3
3 4
4 5
1 6
3 7
6 2

Output 1

1 2 3 2 1 1 1