Три кольори#6676

Три кольори

4 секунди

256 мегабайтів

Дуже складна

Три — це магічне число в інформатиці. Наприклад, розглянемо задачу розфарбування вершин. Легко визначити, чи можна розфарбувати вершини неорієнтованого графа двома кольорами так, щоб жодні дві вершини одного кольору не були з'єднані ребром, але дуже важко це зробити, якщо дозволено використовувати три кольори. Бажаєте ще доказів? Легко розв'язати задачу 2-SAT, але важко 3-SAT.

Це здається несправедливим, тож у цій задачі ми розглянемо просту задачу з трьома кольорами, тоді як варіант із двома кольорами значно складніший.

Розглянемо розфарбування ребер неорієнтованого графа $G$ $k$ кольорами з ${0, 1, \dots, k - 1}$ \{0, 1, \ldots, k-1\}. Позначимо суму кольорів ребер, інцидентних вершині $u$ , як $s (u)$ . Розфарбування називається сусідньо-розрізняючим, якщо для будь-якого ребра, що з'єднує вершини $u$ і $v$ , $s (u) \neq = s (v)$ s(u) \ne s(v).

Задано двочастковий граф $G$ . Знайдіть його сусідньо-розрізняюче $3$ -розфарбування, якщо воно існує.

Вхідні дані

Перший рядок містить три цілі числа $n_{1}$ n_1, $n_{2}$ n_2 та $m$ ( $1 \leq n_{1}, n_{2} \leq 1500$ 1 \le n_1, n_2 \le 1500, $1 \leq m \leq 10000$ 1 \le m \le 10000) — кількість вершин у кожній частині та кількість ребер відповідно. Далі йдуть $m$ рядків з описом ребер: кожне ребро задається двома числами — номерами з'єднаних вершин. У кожній частині вершини нумеруються незалежно, починаючи з $1$ .

Вихідні дані

Якщо у даному графі немає сусідньо-розрізняючого $3$ -розфарбування, виведіть -1.

Інакше виведіть $m$ цілих чисел — кольори ребер у тому порядку, в якому вони подані у вхідних даних.

Приклади

Приклад 1