Lecture Rooms 2

There are N lectures. For each lecture, its start time and end time are given. Use as few lecture rooms as possible while holding every lecture.

A room cannot host two or more lectures at the same time. However, if one lecture ends exactly when another lecture starts, those two lectures may use the same room.

Find the minimum number of rooms K and assign a room number to every lecture.

The first line contains the number of lectures N, where 1 <= N <= 100,000.

Each of the next N lines contains three integers i, s, and e, meaning lecture i starts at time s and ends at time e.

Lecture numbers are from 1 to N. They may appear in any order in the input, but each number appears exactly once. Start and end times are integers between 0 and 1,000,000,000, inclusive, and s < e always holds.

Print the minimum number of rooms K on the first line.

Then print N more lines. For lecture numbers 1 through N in order, print the room number assigned to that lecture. Room numbers must be integers from 1 to K.