AP vốn dĩ là một người thích vẽ nên trước khi khai giảng AP đã kịp mua một bộ màu với ~43 252 003 274 489 856 000~ cây bút màu khác nhau. Tuy nhiên AP lại không phải là người có năng khiếu hội họa nên anh đã làm hỏng gần hết và chỉ còn lại ~200000~ cây bút. Biết tới niềm yêu thích hội họa của AP, thầy giáo môn đồ thị đã đố AP bài toán như sau :

• Cho đồ thị có hướng gồm ~n~ đỉnh và ~m~ cạnh, hãy tìm cách tô màu cho ~m~ cạnh trên đồ thị để không có chu trình nào gồm toàn các cạnh được tô cùng 1 màu.

• Vì sợ AP làm hỏng thêm bút và không thể hoàn thành câu đố nên thầy giáo muốn số màu bút mà cậu sử dụng là ít nhất.

AP đang bận đi khai giảng nên mọi người hãy giúp cậu nhé !! Mai là AP vào lớp một rồi.

Input

• Dòng đầu tiên gồm hai số nguyên ~n~ và ~m~ là số đỉnh và số cạnh của đồ thị. ~(1 \le n \le 2 \times 10^5, 0 \le m \le 2 \times 10^5)~

• ~m~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~u, v~ thể hiện có cạnh từ đỉnh ~u~ tới đỉnh ~v~. ~(1 \le u, v \le 2 \times 10^5, u \neq v)~

Output

• Dòng đầu tiên chứa số nguyên ~k~ là số màu ít nhất cần dùng để giải bài toán của thầy giáo.

• ~m~ dòng tiếp theo, mỗi dòng chứa một số nguyên thể hiện màu được dùng để tô cạnh thứ ~i~ .

• Các màu khác nhau được đánh số lần lượt là ~1, 2, \ldots, k~ .

Subtask

• ~10\%~ số test có ~n \leq 7~.
• ~15\%~ số test không có cạnh nào của đồ thị thuộc quá ~1~ chu trình.
• ~15\%~ số test không có chu trình trong đồ thị.
• Các test còn lại không có điều kiện gì thêm.

Sample Input

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

Sample Output

2
1
2
2
2
2
2

Note

• Từ Sample Input, ta có đồ thị sau: