题目描述

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

输出

2
1
2
1
2
1

---

样例 2

输入

2 4 4
1 1
1 2
1 3
2 4

输出

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$。

---

题目来源：LibreOJ
题号：#3126
时间限制：6000 ms
内存限制：256 MiB
通过：69
提交：234