Phân Phòng Tối Thiểu

Có $n$ lượt sử dụng phòng, lượt $i$ chiếm trọn các ngày từ $a_i$ đến $b_i$. Hai lượt có chung ít nhất một ngày phải dùng hai phòng khác nhau. Hãy dùng ít phòng nhất và đưa ra một cách gán phòng.

Input

• Dòng đầu chứa số nguyên $n$.
• Mỗi trong $n$ dòng tiếp theo chứa hai số nguyên $a_i$ và $b_i$ của một lượt sử dụng.

Output

• Dòng đầu in số phòng tối thiểu $k$.
• Dòng thứ hai in $n$ số nguyên; số thứ $i$ là phòng của lượt $i$. Các phòng được đánh số từ $1$ đến $k$.

Constraints

• $1\le n\le 2\cdot 10^5$.
• $1\le a_i\le b_i\le 10^9$.
• Hai lượt có ngày kết thúc của lượt trước bằng ngày bắt đầu của lượt sau vẫn xung đột.

Scoring

• Subtask $1$ ($50\%$ số điểm): $n\le 10$.
• Subtask $2$ ($50\%$ số điểm): Không có giới hạn bổ sung.

Example

4
1 2
2 3
4 4
3 5

2
1 2 2 1