题目描述

Alan 为了避免感到无聊，便让 Goran 给他出一道有趣的题目。由于他忙于准备考试，Goran 的回忆里只有一个巨大的二分图。他把二分图递给 Alan，让他用尽可能少的颜色涂满所有边，使得同种颜色的边没有公共点。

Goran 看到 Alan 的复杂方法后，决定大发慈悲，给定了一个简化版本：令 $C$ 为上述问题的答案，$X$ 为不小于 $C$ 的最小的 $2$ 的正整数次幂。仅需给出一种方案，使得颜色个数不超过 $X$。

请帮助 Alan 解决该题。

注：二分图是一种能够被分成两个集合的图，使得每条边连接的两个点都属于不同集合。

输入格式

第一行输入正整数 $L,R,M$，分别表示二分图其中第一个集合的点的个数、第二个集合的点的个数和边的个数。

接下来的 $M$ 行，每行输入两个正整数 $a_i,b_i$，表示第一个集合的第 $a_i$ 个点和第二个集合的第 $b_i$ 个点之间有一条边。数据保证，没有重边。

输出格式

第一行输出一个正整数 $K$，表示使用的颜色个数。

接下来的 $M$ 行，每行输出一个正整数 $c_i$（$1 \le c_i \le K$），表示第 $i$ 条边所用颜色。

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

2
1
2
1
2
1

2 4 4
1 1
1 2
1 3
2 4

4
1
2
3
4

提示

样例 2 解释

使用颜色最少个数为 $3$。然而，使用 $4$ 种颜色也是可行的。因为 $4$ 是不小于 $3$ 的最小的 $2$ 的正整数次幂。

数据规模与约定

对于 $20\%$ 的数据，$L,R \le 100$。

对于另外 $20\%$ 的数据，$L,R \le 5000$。

对于 $100\%$ 的数据，$1 \le L,R \le 10^5$，$1 \le M \le 5 \times 10^5$，$1 \le a_i \le L$，$1 \le b_i \le R$。

说明

这里只选取其中具有梯度的 $10$ 个测试点进行评测，因此满分由 $130$ 调整为 $100$。

题目译自 COCI2018-2019 CONTEST #1 T5 Teoretičar。