Диспетчер автопарка должен распределить n рейсов между автобусами.

Для каждого рейса известны момент отправления s_i и момент завершения e_i, где s_i < e_i. Один и тот же автобус не может одновременно выполнять несколько рейсов. Если автобус завершил один рейс в момент e, то следующий рейс он может начать не раньше этого же момента.

Требуется назначить каждому рейсу автобус так, чтобы использовалось минимально возможное количество автобусов. Необходимо вывести любое корректное распределение.

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

Первая строка содержит одно целое число n — количество рейсов.

В следующих n строках содержатся по два целых числа s_i и e_i — моменты начала и окончания i-го рейса.

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

В первой строке выведите одно целое число k — минимальное количество автобусов, необходимое для выполнения всех рейсов.

Во второй строке выведите n целых чисел b_1, b_2, ..., b_n, где b_i — номер автобуса, назначенного i-му рейсу в исходном порядке.

Нумерация автобусов может быть любой, если выполняются условия:

• 1 <= b_i <= k;
• все рейсы, назначенные одному автобусу, не пересекаются по времени;
• если один рейс заканчивается в тот же момент, когда начинается другой, их можно выполнять одним автобусом.

Если существует несколько решений, разрешается вывести любое.

Ограничения

• 1 <= n <= 2 * 10^5
• 0 <= s_i < e_i <= 10^9

Примеры

Пример 1

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

1
0 1

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

1
1

Пример 2

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

4
1 4
4 7
2 3
3 5

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

2
1 1 2 2