Edge Coloring of a Bipartite Graph

Problem: Given a bipartite graph with two disjoint vertex sets (left and right), your task is to assign a color to every edge such that no two edges sharing a common vertex have the same color. Let C be the minimum number of colors required (i.e. the optimal edge chromatic number) and let X be the smallest positive integer power of 2 that is not less than C. You only need to provide a valid coloring that uses no more than X colors.

Input:
The first line contains three integers n1, n2, and m, where n1 and n2 denote the number of vertices in the left and right sets, respectively, and m is the number of edges. Each of the next m lines contains two integers u and v indicating an edge between vertex u in the left set and vertex v in the right set.

Output:
The first line should output the number of colors used (this number must be ≤ X). In the following m lines, output one integer per line which is the color assigned to the corresponding edge in the input order.

Note:
A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex from one set to a vertex from the other set.

inputFormat

The first line contains three integers: n1, n2, and m. Then follow m lines, each containing two integers u and v representing an edge from u (in the left set) to v (in the right set).

outputFormat

First, output the number of colors used. Then output m lines, each containing the color (an integer) assigned to the corresponding edge in the input order. The total number of colors used must not exceed X, where X is the smallest power of 2 not less than C (the optimum number of colors).

sample

2 2 3
1 1
1 2
2 1

2
2
1
1