Bố trí Phòng Khách sạn

Một khách sạn cần bố trí phòng cho $n$ khách. Hai khách có thể ở chung một phòng nếu ngày rời đi của khách thứ nhất thực sự sớm hơn ngày đến của khách thứ hai. Hãy tìm số phòng tối thiểu cần dùng và gán mỗi khách vào một phòng.

Dữ liệu vào

• Dòng đầu: số nguyên $n$ — số lượng khách.
• $n$ dòng tiếp theo, dòng thứ $i$: hai số nguyên $a_i$ và $b_i$ — ngày đến và ngày rời đi của khách $i$ ($1\le a_i\le b_i\le {10}^9$).

Dữ liệu ra

• Dòng 1: số nguyên $k$ — số phòng tối thiểu cần dùng.
• Dòng 2: $n$ số nguyên (từ 1 đến $k$) — phòng được gán cho mỗi khách theo thứ tự đầu vào.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le a_i\le b_i\le {10}^9$

Ví dụ