CF600F.Edge coloring of bipartite graph

You are given an undirected bipartite graph without multiple edges. You should paint the edges of graph to minimal number of colours, so that no two adjacent edges have the same colour.

给你一个无向二分图，且不含重边。你需要用最少的颜色对图的边进行染色，使得任意两条相邻的边颜色不同。

The first line contains three integers a, b, m (1 ≤ a, b ≤ 1000, 0 ≤ m ≤ 105), a is the size of the first part, b is the size of the second part, m is the number of edges in the graph.

Each of the next m lines contains two integers x, y (1 ≤ x ≤ a, 1 ≤ y ≤ b), where x is the number of the vertex in the first part and y is the number of the vertex in the second part. It is guaranteed that there are no multiple edges.

第一行包含三个整数 $a$、$b$、$m$（$1 \le a, b \le 1000$，$0 \le m \le 10^5$），其中 $a$ 是二分图第一部分的顶点数，$b$ 是第二部分的顶点数，$m$ 是图中的边数。

接下来的 $m$ 行每行包含两个整数 $x$、$y$（$1 \le x \le a$，$1 \le y \le b$），其中 $x$ 表示第一部分中顶点的编号，$y$ 表示第二部分中顶点的编号。保证图中不存在重边。

In the first line print integer c — the minimal number of colours. The second line should contain m integers from 1 to c — the colours of the edges (in the order they appear in the input).

If there are several solutions, you can print any one of them.

第一行输出整数 $c$ —— 所需的最少颜色数。
第二行应包含 $m$ 个介于 $1$ 到 $c$ 之间的整数 —— 各条边的颜色（按输入中出现的顺序）。

若存在多种解，输出任意一种即可。