Cho một đồ thị hai phía vô hướng và không có cạnh trùng. Hãy tô màu các cạnh của đồ thị với số lượng màu tối thiểu, sao cho hai cạnh kề nhau được tô bằng hai màu khác nhau.

Input

Dòng đầu tiên gồm ba số nguyên ~a, b~ và ~m~ ~(1 \le a, b \le 1000, 0 \le m \le 10^5)~ với ~a~ là số đỉnh của phần thứ nhất, ~b~ là số đỉnh của phần thứ hai, và ~m~ là số cạnh trong đồ thị.

~m~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~x~ và ~y~ ~(1 \le x \le a, 1 \le y \le b)~ thể hiện một cạnh trong đồ thị với ~x~ là thứ tự của đỉnh trong phần thứ nhất, và ~y~ là thứ tự của đỉnh trong phần thứ hai. Đảm bảo đồ thị sẽ không có cạnh trùng.

Output

Dòng đầu tiên in ra một số nguyên ~c~ là số lượng màu tối thiểu cần.

Dòng thứ hai in ra ~m~ số nguyên trong khoảng ~[1, c]~ là màu của các cạnh theo thứ tự input đã cho.

Nếu có nhiều đáp án, hãy in ra một trong số chúng.

Sample

Input

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

Output

3
1 2 3 1 2

Giải thích

Một cách tô màu là như sau:

với màu vàng là ~1~, màu xanh lá là ~2~, và màu đỏ là ~3~.