Mô tả bài toán: Phân vùng các hành tinh

Một trò chơi có n hành tinh, được kết nối bởi m thiết bị dịch chuyển tức thời. Hai hành tinh ~a~ và ~b~ thuộc cùng một vương quốc nếu và chỉ nếu có đường đi từ ~a~ đến ~b~ và từ ~b~ đến ~a~. Nhiệm vụ của bạn là xác định mỗi hành tinh thuộc vương quốc nào.

Input:

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~m~: số lượng hành tinh và số lượng thiết bị dịch chuyển.
• Tiếp theo, có ~m~ dòng, mỗi dòng chứa hai số nguyên ~a~ và ~b~: bạn có thể di chuyển từ hành tinh ~a~ đến hành tinh ~b~ thông qua một thiết bị dịch chuyển.

Output:

• Dòng đầu tiên in số nguyên ~k~: số lượng vương quốc.
• Sau đó, in ~n~ số nguyên, mỗi số nguyên nằm trong đoạn từ ~1~ đến ~k~, đại diện cho nhãn của vương quốc của từng hành tinh.

Ràng buộc:

• ~1 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a, b \leq n~

Ví dụ:

Input:

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

Output:

2
1 1 1 2 2

Giải thích:

• Có hai vương quốc:
  • Vương quốc 1: Các hành tinh ~1, 2, 3~ (liên thông và có thể di chuyển qua lại).
  • Vương quốc 2: Các hành tinh ~4, 5~ (liên thông và có thể di chuyển qua lại).