Three Colors#6676
Three is a magic number in computer science. For example, consider the vertex coloring problem. It is easy to decide whether you can color the vertices of an undirected graph using two colors so that no two vertices of the same color are joined by an edge, but it is very hard to do so if you are allowed to use three colors. Want more evidence? It is easy to solve 2-SAT, but it is hard to solve 3-SAT.
This seems unfair, so in this problem, we consider an easy problem involving three colors, while the version with two colors is more difficult.
Consider coloring the edges of an undirected graph using colors from \{0, 1, \ldots, k-1\}. Denote the sum of the colors of edges incident to a vertex as . We say that an edge coloring is neighbor distinguishing if for every edge connecting two vertices and , s(u) \ne s(v).
Given a bipartite graph , find its neighbor distinguishing -coloring if it exists.
The first line contains three integers n_1, n_2 and (1 \le n_1, n_2 \le 1500, 1 \le m \le 10000) — the number of vertices in each part, and the number of edges, respectively. The next lines describe the edges; each edge is described by two integers — the numbers of the vertices it connects. Vertices in each part are independently numbered starting from .
If the given graph has no neighbor distinguishing -coloring, output -1.
Otherwise, output integers — the colors of the edges in the order they are listed in the input.
Example 1