You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

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。