Three Colors
Three is like magic number in computer science. For example, consider vertex coloring problem. It is easy to detect whether you can color vertices of an undirected graph using two colors so that no vertices of the same color are connected by an edge, but it is very hard to do it if you are allowed to use three colors. Asking for more? It is easy to solve 2-SAT but it is hard to solve 3-SAT.
It is unfair, so in this problem we consider an easy problem with three colors while the problem with two colors is more diffi cult.
Consider coloring edges of an undirected G using k colors from {0, 1, ..., k-1}. Denote the sum of colors of edges incident to vertex u as s(u). The coloring is called neighbor distinguishing if for any two vertices u and v connected by an edge s(u) ≠ s(v).
Given a bipartite graph G you must find its neighbor distinguishing 3-coloring.
Input
The first line of the input fole contains three integer numbers n_1, n_2 and m - the number of vertices in each part and the number of edges, respectively (1 ≤ n_1, n_2 ≤ 1500, 1 ≤ m ≤ 10000). The following m lines describe edges, each edge is described by two integer numbers - the numbers of vertices it connects. Vertices in each part are independently numbered starting from 1.
Output
If the given graph has no neighbor distinguishing 3-coloring, output -1.
In the other case output m integer numbers the colors of the edges in order they are described in the input file.