Bài toán: Sắp xếp phòng khách sạn

Đề bài

Cho một khách sạn với ~ n ~ khách hàng sắp đến. Mỗi khách cần một phòng. Biết ngày đến và ngày rời đi của từng khách hàng. Hai khách có thể dùng chung một phòng nếu ngày rời đi của khách đầu tiên trước ngày đến của khách thứ hai.

Yêu cầu:

1. Tìm số lượng phòng tối thiểu cần thiết để sắp xếp tất cả khách hàng.
2. Gán số phòng cho từng khách sao cho không xảy ra xung đột về lịch.

Input

• Dòng đầu tiên chứa số nguyên ~ n ~ (~ 1 \leq n \leq 2 \times 10^5 ~): số lượng khách.
• ~ n ~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~ a, b ~ (~ 1 \leq a \leq b \leq 10^9 ~): ngày đến và ngày đi của từng khách.

Output

• In ra số nguyên ~ k ~: số lượng phòng tối thiểu cần thiết.
• In ra một dòng chứa ~ n ~ số nguyên: số phòng của từng khách hàng, theo thứ tự như đầu vào.

Ràng buộc

• ~ 1 \leq n \leq 2 \times 10^5 ~
• ~ 1 \leq a \leq b \leq 10^9 ~

Ví dụ

Input:

3
1 2
2 4
4 4

Output:

2
1 2 1