Є великий готель, і ~n~ клієнтів скоро приїде. Кожен клієнт хоче мати одномісну кімнату. Ви знаєте день прибуття та від'їзду кожного клієнта. Два клієнти можуть проживати в одному номері, якщо день виїзду першого клієнта раніше дня прибуття другого.

Яка мінімальна кількість кімнат необхідна для розміщення всіх клієнтів? І як можна розподілити кімнати?

Обмеження

• ~1≤n≤2⋅10^5~
• ~1 ≤ a ≤ b ≤ 10^9~

Формат вхідних даних

Перший рядок містить ціле число ~n~: кількість клієнтів.

Потім є ~n~ рядків, кожен з яких описує одного клієнта.

У кожному рядку є два цілих числа ~a~ і ~b~: день прибуття та від'їзду.

Формат вихідних даних

Виведіть спочатку ціле число ~k~: мінімальна необхідна кількість кімнат.

Після цього виведіть рядок, який містить номер кімнати кожного клієнта в тому ж порядку, що й у вхідних даних. Кімнати пронумеровані ~1,2,…,k~. Ви можете роздрукувати будь-яке дійсне рішення.

Приклад вхідних даних

3
1 2
2 4
4 4

Приклад вихідних даних

2
1 2 1