Три цвета

Число три в информатике играет ключевую роль. Часто некоторые задачи легко решаются, если некоторый параметр в задаче равен двум или одному, но становятся сложными, если этот параметр равен трем. Например, задача о раскраске графа в два цвета --- это проверка на двудольность, а раскраска в три цвета --- трудная задача.

Мы решили, что это нечестно и придумали задачу, которая легко решается для трех цветов, но гораздо труднее для двух.

Рассмотрим двудольный граф $G$, разрешим раскрашивать его ребра в три цвета: 0, 1 и 2. Будем обозначать сумму цветов ребер, один из концов которых равен $u$, как $s(u)$. Будем называть такую раскраску различающей соседей, если для любых двух вершин $u$ и $v$, соединенных ребром, выполнено неравенство $s(u) \ne s(v)$.

По заданному двудольному графу $G$ найдите его раскраску в три цвета, различающую соседей.

Первая строка входного файла содержит три целых числа $n_1$, $n_2$ и $m$ --- количество вершин в каждой из долей и количество ребер в графе, соответственно ($1 \le n_1, n_2 \le 1500$, $1 \le m \le 10000$).

Следующие $m$ строк описывают ребра, каждое ребро описывается двумя целыми числами --- номерами вершин, которые оно соединяет. Вершины в каждой доле независимо нумеруются, начиная с единицы.

Если решения не существует, выведите <<$-1$>>.

Иначе выведите $m$ целых чисел --- цвета ребер. Выводите цвета ребер в порядке, в котором ребра заданы во входном файле.