F. Раскраска ребер двудольного графа
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Задан неориентированный двудольный граф без кратных ребер. Требуется покрасить его ребра в минимальное количество цветов так, чтобы никакие два одноцветных ребра не были инцидентны одной вершине.

Инцидентность — понятие, используемое в отношении ребра и вершины. Ребро инцидентно вершине, если вершина является одним из концов этого ребра.

Входные данные

В первой строке записаны три целых числа a, b, m (1 ≤ a, b ≤ 1000, 0 ≤ m ≤ 105), a — размер первой доли, b — размер второй доли, m — количество ребер.

Далее в m строках заданы ребра графа парами номеров соединяемых вершин x, y (1 ≤ x ≤ a, 1 ≤ y ≤ b), где x — номер вершины в первой доле, а y — во второй. Гарантируется, что между каждой парой вершин существует не более одного ребра.

Выходные данные

В первую строку выведите число c — минимальное количество цветов. Вторая строка должна содержать последовательность m целых чисел от 1 до c — цвета ребер (в порядке их появления во входных данных).

Если решений несколько, выведите любое.

Примеры
Входные данные
4 3 5
1 2
2 2
3 2
4 1
4 3
Выходные данные
3
1 2 3 1 2