题目描述

译自 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

input

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

output

2
1
2
1
2
1

样例 2

input

2 4 4
1 1
1 2
1 3
2 4

output

4
1
2
3
4

注意此二分图的最优方案是 $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$。