Cho một đồ thị đơn có \(n\) đỉnh và \(m\) cạnh. Nhiệm vụ của bạn là dùng số màu ít nhất có thể để tô màu mỗi đỉnh sao cho không có cạnh nào nối hai đỉnh cùng màu.

Input

Dòng đầu tiên chứa hai số nguyên \(n\) và \(m\): số đỉnh và số cạnh. Các đỉnh được đánh số \(1, 2,\dots, n\).

Sau đó có \(m\) dòng mô tả các cạnh. Mỗi dòng chứa hai số nguyên \(a\) và \(b\): có một cạnh nối hai đỉnh \(a\) và \(b\).

Output

Đầu tiên, in ra một số nguyên \(k\): số màu nhỏ nhất.

Sau đó, in ra \(n\) số nguyên \(c_1, c_2,\dots, c_n\): màu của các đỉnh. Các màu phải thỏa mãn \(1 \le c_i \le k\).

Bạn có thể in ra bất kỳ lời giải hợp lệ nào.

Constraints

• \(1 \le n \le 16\)

• \(0 \le m \le \frac{n(n-1)}{2}\)

Example

4 4
1 2
2 3
3 4
4 1

2
1 2 1 2