Три - це магічне число у галузі комп'ютерних наук. Розглянемо, наприклад, проблему розфарбування вершин. Легко розв'язати задачу розфарбування вершин неорієнтовного графа двома кольорами так, щоб ніякі вершини одного кольору не були з'єднані ребром. Проте задача стає важкою, якщо дозволено використовувати три кольори. Хочете ще підтверджень? Легко розв'зати задачу \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} цілих чисел - кольори ребер у тому ж порядку, у якому вони поступають на вхід.