Time limit: 1.00 s Memory limit: 512 MB
There is a large hotel, and
You know each customer's arrival and departure day. Two customers can stay in the same room if the departure day of the first customer is earlier than the arrival day of the second customer.
What is the minimum number of rooms that are needed to accommodate all customers? And how can the rooms be allocated?
Input
The first input line contains an integer
Then there are
Output
Print first an integer
After that, print a line that contains the room number of each customer in the same order as in the input. The rooms are numbered
Constraints
$1 \le n \le 2 \cdot 10^5$ $1 \le a \le b \le 10^9$
Example
Input:
3
1 2
2 4
4 4
Output:
2
1 2 1