← 返回题目列表

Codeforces · 600/F

F. 二分图的边缘着色

中文机器翻译题面 查看原题

给你一个没有多条边的无向二分图。您应该将图形的边缘绘制为最少数量的颜色,以便没有两个相邻的边缘具有相同的颜色。

输入

第一行包含三个整数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