Có một khách sạn lớn, và \(n\) khách hàng sẽ đến sớm. Mỗi khách hàng muốn có một phòng đơn.

Bạn biết ngày nhận phòng và trả phòng của mỗi khách hàng. Hai khách hàng có thể ở trong cùng một phòng nếu ngày trả phòng của khách hàng đầu tiên sớm hơn ngày nhận phòng của khách hàng thứ hai.

Số lượng phòng tối thiểu cần thiết để chứa tất cả khách hàng là bao nhiêu? Và các phòng có thể được phân bổ như thế nào?

Input

• Dòng đầu vào đầu tiên chứa một số nguyên n: số lượng khách hàng.
• Sau đó, có \(n\) dòng, mỗi dòng mô tả một khách hàng. Mỗi dòng có hai số nguyên \(a\) và \(b\): ngày nhận phòng và trả phòng.

Output

• In đầu tiên một số nguyên \(k\): số phòng tối thiểu cần thiết.
• Sau đó, in một dòng chứa số phòng của mỗi khách hàng theo thứ tự giống như trong đầu vào. Các phòng được đánh số \(1,2,\ldots,k\). Bạn có thể in bất kỳ giải pháp hợp lệ nào.

Constraints

• \(1 \le n \le 2 \cdot 10^5\)
• \(1 \le a \leq b \le 10^9\)

Example

Sample input

3
1 2
2 4
4 4

Sample output

2
1 2 1