Маленькому Алану было скучно, поэтому он попросил Горана дать ему интересную задачу. Так как он занят подготовкой к экзаменам, Горан мог вспомнить только один огромный двудольный граф из своих старых дней, когда он соревновался в программировании. Он дал граф Алану и сказал: "Вы должны раскрасить ребра этого двудольного графа, используя как можно меньше цветов таким образом, чтобы не было двух ребер одного цвета, имеющих общий узел".

Алан взволнованно побежал к себе в комнату, достал свое передвижное устройство чтения/записи для ленты и начал работать над проблемой. Однако вскоре он понял, что что-то упускает, поэтому вернулся к Горану и сказал: "Дайте мне бесконечную ленту, и я решу вашу проблему"! Горан многозначительно посмотрел на него: "Бесконечная лента? Если вы продолжите теоретизировать обо всем, не будет ни одной вещи, названной в Вашу честь". Увидев, что Алан начинает плакать, Горан решил проявить милосердие: я немного облегчу вам задачу. Пусть $c$ будет наименьшим количеством цветов, необходимых для раскраски графа описанным способом. Я позволю вам использовать не более $x$ цветов, где $x$ - наименьшая степень $2$, не меньше $c$.

Помогите Алану решить проблему.

Примечание. Двудольный граф - это граф, узлы которого можно разделить на два множества (или стороны) таким образом, что каждое ребро графа соединяет один узел из первого множества с одним узлом из второго множества.

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

Первая строка содержит три натуральных числа: $l$, $r$ и $m$ ($1 ≤ l, r ≤ 10^5$, $1 ≤ m ≤ 500000$ ), представляющее количество узлов с одной стороны двудольного графа, количество узлов с другой стороны двудольного графа и количество ребер в графе. Далее следуют $m$ строк, каждая из которых содержит два положительных целых числа $a_i$ ($1 ≤ a_i ≤ l$) и $b_i$ ($1 ≤ b_i ≤ r$), которые представляют ребро между $a_i$-м узлом первой стороны и $b_i$-м узлом второй стороны двудольного графа. Все пары ($a_i$, $b_i$) являются уникальными.

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

В первой строке выведите натуральное число $k$ - количество используемых цветов.

В следующих $m$ строках выведите натуральные числа $c_i$ ($1 ≤ c_i ≤ k$) - метки цвета $i$-го ребра.

Пояснение

Рассмотрим второй тест. Минимальное количество цветов равно $3$. Однако использование $4$ цветов также допустимо, поскольку это наименьшая степень $2$, которая не меньше $3$.