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$ là số phòng tối thiểu cần dùng.
• Dòng 2: $n$ số nguyên trong đoạn $[1,k]$, số thứ $i$ là phòng được gán cho khách $i$.

Nếu có nhiều cách bố trí dùng đúng $k$ phòng, in ra một cách bất kỳ.

Ràng buộc

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

Ví dụ