二分图边着色（Edge Coloring of Bipartite Graph）

问题描述

给定一个无向二分图，左部有 $L$ 个顶点，右部有 $R$ 个顶点，共 $M$ 条边。第 $i$ 条边连接左部顶点 $a_i$ 与右部顶点 $b_i$。
求该图的边染色，使得任意两条共享顶点的边颜色不同，并使所用颜色数最少（即达到边色数）。

约束条件

• $1 \leq L, R \leq 10^5$
• $1 \leq M \leq 10^5$
• $0 \leq a_i < L$
• $0 \leq b_i < R$

输入

$L\ R\ M$
$a_0\ b_0$
$a_1\ b_1$
:
$a_{M-1}\ b_{M-1}$

输出

$K$
$c_0$
$c_1$
:
$c_{M-1}$

$K$ 是边色数（即最小颜色数），$c_i$ 是第 $i$ 条边的颜色编号，满足 $0 \le c_i < K$。

4 4 7
1 1
2 2
0 0
3 1
1 2
2 0
3 2

3
0
2
1
2
1
0