Edge coloring of bipartite graph

Description:

Input:

The first line contains three integers a, b, m (1 ≤ a, b ≤ 1000, 0 ≤ m ≤ 10⁵), 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.

Output:

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.

Sample Input:

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

Sample Output:

3
1 2 3 1 2