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

Алан схвильовано побіг до себе в кімнату, дістав свій пересувний пристрій для читання/запису для стрічки і почав працювати над проблемою. Однак незабаром він зрозумів, що щось упускає, тому повернувся до Горана і сказав: "Дайте мені нескінченну стрічку, і я вирішу вашу проблему"! Горан багатозначно подивився на нього: "Безкінечна стрічка? Якщо ви продовжите теоретизувати про все, не буде жодної речі, названої на Вашу честь". Побачивши, що Алан починає плакати, Горан вирішив виявити милосердя: я трохи полегшу вам завдання. Нехай $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$.