Description

To avoid feeling bored, Alan asked Goran to come up with an interesting problem. Since he was busy preparing for exams, Goran only remembered a huge bipartite graph. He gave the bipartite graph to Alan and asked him to color all edges using as few colors as possible, such that edges of the same color do not share a common endpoint.

After seeing Alan’s complicated method, Goran decided to be merciful and gave a simplified version: let $C$ be the answer to the problem above, and let $X$ be the smallest positive integer power of $2$ that is not less than $C$. You only need to output one coloring scheme that uses no more than $X$ colors.

Please help Alan solve this problem.

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

Input Format

The first line contains positive integers $L, R, M$, representing the number of vertices in the first set of the bipartite graph, the number of vertices in the second set, and the number of edges.

In the next $M$ lines, each line contains two positive integers $a_i, b_i$, meaning there is an edge between the $a_i$-th vertex in the first set and the $b_i$-th vertex in the second set. The testdata guarantees that there are no multiple edges.

Output Format

The first line outputs a positive integer $K$, the number of colors used.

In the next $M$ lines, output a positive integer $c_i$ ($1 \le c_i \le K$) on each line, representing the color used for the $i$-th edge.

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

Hint

Sample 2 Explanation

The minimum number of colors needed is $3$. However, using $4$ colors is also feasible, because $4$ is the smallest positive integer power of $2$ that is not less than $3$.

Constraints

For $20\%$ of the testdata, $L, R \le 100$.

For another $20\%$ of the testdata, $L, R \le 5000$.

For $100\%$ of the testdata, $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$.

Notes

Only $10$ graded test points are used for evaluation here, so the full score is adjusted from $130$ to $100$.

This problem is translated from COCI2018-2019 CONTEST #1 T5 Teoretičar.

Translated by ChatGPT 5