#3126. 「COCI 2018.10」Teoretičar

内存限制:256 MiB 时间限制:6000 ms 标准输入输出
题目类型:传统 评测方式:Special Judge
上传者: EntropyIncreaser

题目描述

译自 COCI 2018/2019 Contest #1 T5「Teoretičar

有这样一个二分图上的问题:给你一个二分图,请用尽量少的颜色给边染色,使得每个顶点的出边颜色互不相同。

你只需要解决这个问题的放宽限制的版本,现在假设对于给定二分图的答案是 C ,记 X 是大于等于 C 的最小的 2 的整次幂,你只需要给出一个方案,使得颜色数量不多于 X

输入格式

第一行三个正整数 L, R, M ,表示二分图左部点数,右部点数以及边数。

接下来 M 行,每行两个整数 a_i, b_i(1\le a_i \le L, 1\le b_i \le R) ,表示左部到右部的一条连边。保证没有重边。

输出格式

第一行输出一个正整数 K ,表示你所用的颜色数。

接下来 M 行每行一个正整数 c_i(1\le c_i \le K) ,表示第 i 条边的颜色。

样例

样例输入 1

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

样例输出 1

2
1
2
1
2
1

样例输入 2

2 4 4
1 1
1 2
1 3
2 4

样例输出 2

4
1
2
3
4

样例解释 2

注意此二分图的最优方案是 3 种颜色,因此 4 种颜色也符合条件。

数据范围与提示

对于 20\% 的数据,保证 L, R \le 100

对于 40\% 的数据,保证 L, R \le 5 \times 10^3

对于 100\% 的数据,保证 1\le L, R\le 10^5, 1\le M \le 5\times 10^5