Màu yêu thích

Có $N$ con bò và $M$ quan hệ "ngưỡng mộ" ($b$ ngưỡng mộ $a$). Ràng buộc: nếu $x$ và $y$ cùng ngưỡng mộ một bò có màu $c$, thì $x$ và $y$ phải có cùng màu. Gán màu (số nguyên) cho mỗi bò sao cho số màu phân biệt lớn nhất, và phép gán có thứ tự từ điển nhỏ nhất.

Dữ liệu vào

• Dòng đầu: $N$ và $M$.
• $M$ dòng tiếp: $a$, $b$ (bò $b$ ngưỡng mộ bò $a$).

Dữ liệu ra

• $N$ dòng, dòng $i$ là màu của bò $i$.

Ràng buộc

• $1\le N,M\le 2\times {10}^5$

Ví dụ