Три - это магическое число в области компьютерных наук. Рассмотрим, например, проблему окраски вершин. Легко решить задачу покраски вершин неориентированного графа двумя цветами так, чтобы никакие вершины одного цвета не были соединены ребром. Однако задача становится трудной, если разрешено использовать три цвета. Хотите еще доказательств? Легко решить задачу \textbf{2}-Выполнимость, но трудно решить \textbf{3}-Выполнимость. Хотя это и несправедливо, но здесь мы рассмотрим простую задачу с тремя цветами, в то время как задача с двумя цветами намного сложнее. Рассмотрим раскраску ребер неориентированного графа \textbf{G} при помощи \textbf{k} цветов с номерами \textbf{\{0, 1, ..., k-1\}}. Сумму цветов ребер, инцидентных вершине \textbf{u}, обозначим через \textbf{s(u)}. Раскраску будем называть \textit{соседски различимой}, если для любых двух вершин \textbf{u} и \textbf{v}, соединенных ребром, имеет место \textbf{s(u) }≠\textbf{ s(v)}. По заданному двудольному графу \textbf{G} необходимо найти \textit{соседски различимую} \textbf{3}-раскраску. \InputFile Первая строка содержит три целых числа \textbf{n_1}, \textbf{n_\{2 \}}и \textbf{m }(\textbf{1} ≤ \textbf{n_1}, \textbf{n_2} ≤ \textbf{1500}, \textbf{1} ≤ \textbf{m} ≤ \textbf{10000}) - количество вершин в каждой из частей графа и количество ребер соответственно. Каждая из следующих \textbf{m} строк описывает ребро и содержит два числа - номера вершин, которые оно соединяет. В каждой части графа вершины независимо пронумерованы начиная с \textbf{1}. \OutputFile Если граф не имеет соседски различимой \textbf{3}-раскраски, выведите \textbf{-1}. Иначе выведите \textbf{m} целых чисел - цвета ребер в том же порядке, как они поступают на вход.