Một trò chơi có \(n\) hành tinh, được kết nối bởi \(m\) cổng dịch chuyển. Hai hành tinh \(a\) và \(b\) thuộc cùng một vương quốc chỉ khi có một lộ trình cả từ \(a\) đến \(b\) và từ \(b\) đến \(a\). Nhiệm vụ của bạn là xác định vương quốc cho mỗi hành tinh.

Input

• Dòng đầu vào đầu tiên có hai số nguyên \(n\) và \(m\) \((1 \leq n \leq 10^{5}, 1 \leq m \leq 2 \times 10^{5})\) - số lượng hành tinh và cổng dịch chuyển. Các hành tinh được đánh số \(1, 2, \ldots, n\).
• Sau này, có \(m\) dòng mô tả các cổng dịch chuyển. Mỗi dòng có hai số nguyên \(a\) và \(b\) \((1 \leq a, b \leq n)\) - bạn có thể đi từ hành tinh \(a\) đến hành tinh \(b\) thông qua một cổng dịch chuyển.

Output

• Đầu tiên in một số nguyên \(k\): số lượng vương quốc. Sau đó, in chỉ số vương quốc từ \(1\) đến \(k\) cho mỗi hành tinh. Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Example

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

2
1 1 1 2 2