小 Alan 觉得很无聊，于是让 Goran 给他出一个有趣的问题。由于 Goran 正忙于准备考试，他只记得自己以前作为算法竞赛选手时遇到过的一个巨大的二分图。他把这个图给了 Alan 并说道：“你需要用尽可能少的颜色给这个二分图的边染色，使得任意两条共用同一个节点的边颜色不同。”

Alan 兴奋地跑到自己的房间，拿出用于纸带的可移动读写设备，开始研究这个问题。然而，他很快意识到自己缺少了一些东西，于是他回去找 Goran 并说道：“给我一条无限长的纸带，我就能解决你的问题！”Goran 意味深长地看了他一眼：“无限长的纸带？如果你对所有事情都继续进行纯理论研究，那么将不会有任何一样东西是以你的名字命名的。”

看到 Alan 快要哭出来了，Goran 决定发发慈悲：“我让这个问题变得简单一点。设 $C$ 是以所述方式给图染色所需的最少颜色数。我允许你最多使用 $X$ 种颜色，其中 $X$ 是不小于 $C$ 的最小的 $2$ 的幂。”

帮助 Alan 解决这个问题。

注意：二分图是指一个图，其节点可以被分为两个集合（或两边），使得图中的每条边都连接第一个集合中的一个节点和第二个集合中的一个节点。

输入格式

第一行包含三个正整数：$L, R$ 和 $M$（$1 \le L, R \le 100\,000$，$1 \le M \le 500\,000$），分别表示二分图左侧的节点数、右侧的节点数和边数。

接下来的 $M$ 行，每行包含两个正整数 $a_i$（$1 \le a_i \le L$）和 $b_i$（$1 \le b_i \le R$），表示二分图左侧的第 $a_i$ 个节点与右侧的第 $b_i$ 个节点之间的一条边。所有数对 $(a_i, b_i)$ 都是唯一的。

输出格式

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

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

子任务

• 在占总分 20% 的测试数据中，满足 $L, R \le 100$。
• 在另外占总分 20% 的测试数据中，满足 $L, R \le 5\,000$。

样例

输入样例 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$ 种颜色也是可以接受的，因为 $4$ 是不小于 $3$ 的最小的 $2$ 的幂。