Hành Tinh và Vương Quốc

Có $n$ hành tinh và $m$ cổng dịch chuyển một chiều. Hai hành tinh thuộc cùng một vương quốc nếu có đường đi từ $a$ đến $b$ và từ $b$ đến $a$. Hãy xác định mỗi hành tinh thuộc vương quốc nào.

Dữ liệu vào

• Dòng 1: hai số nguyên $n$ và $m$.
• $m$ dòng tiếp theo: mỗi dòng gồm hai số nguyên $a$ và $b$ — cổng dịch chuyển một chiều từ $a$ đến $b$.

Dữ liệu ra

• Dòng 1: số nguyên $k$ — số vương quốc.
• Dòng 2: $n$ số nguyên — nhãn vương quốc của mỗi hành tinh (từ 1 đến $k$).

Ràng buộc

• $1\le n\le {10}^5$
• $1\le m\le 2\times {10}^5$
• $1\le a,b\le n$

Ví dụ