给你一个没有多条边的无向二分图。您应该将图形的边缘绘制为最少数量的颜色,以便没有两个相邻的边缘具有相同的颜色。
输入
第一行包含三个整数a、b、m(1 ≤ a、b ≤ 1000、0 ≤ m ≤ 105),a 是第一部分的大小,b 是第二部分的大小,m 是图中的边数。
接下来的 m 行每行包含两个整数 x, y (1 ≤ x ≤ a, 1 ≤ y ≤ b),其中 x 是第一部分中的顶点编号,y 是第二部分中的顶点编号。保证不存在重边。
输出
在第一行打印整数 c — 最小颜色数。第二行应包含 m 个从 1 到 c 的整数——边缘的颜色(按照它们在输入中出现的顺序)。
如果有多个解决方案,您可以打印其中任何一个。
示例
输入 #1
4 3 5 1 2 2 2 3 2 4 1 4 3
输出 #1
3 1 2 3 1 2