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 difficult. Consider coloring edges of an undirected \textbf{G} using \textbf{k} colors from \textbf{\{0, 1, ..., k-1\}}. Denote the sum of colors of edges incident to vertex \textbf{u} as \textbf{s(u)}. The coloring is called \textit{neighbor distinguishing} if for any two vertices \textbf{u} and \textbf{v} connected by an edge \textbf{s(u) }≠\textbf{ s(v)}. Given a bipartite graph \textbf{G} you must find its neighbor distinguishing \textbf{3}-coloring. \InputFile The first line of the input fole contains three integer numbers \textbf{n_1}, \textbf{n_2} and \textbf{m} - the number of vertices in each part and the number of edges, respectively (\textbf{1} ≤ \textbf{n_1}, \textbf{n_2} ≤ \textbf{1500}, \textbf{1} ≤ \textbf{m} ≤ \textbf{10000}). The following \textbf{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 \textbf{1}. \OutputFile If the given graph has no neighbor distinguishing \textbf{3}-coloring, output \textbf{-1}. In the other case output \textbf{m} integer numbers  the colors of the edges in order they are described in the input file.