Milking Scheduling

Farmer John (or John) has N cows (where \(1\le N\le 50{,}000\)), and each cow has a specific milking time interval \([A,B]\) (with \(1\le A\le B\le 1{,}000{,}000\), and the endpoints A and B are included). Since no two cows can be milked in the same stall at the same time (even if one cow’s milking period ends exactly when another begins, the moment they share, even at the boundary, is considered a conflict), you are to help determine the minimum number of stalls required and assign a stall to each cow so that all cows get their private milking session.

Many assignments can achieve the minimum number of stalls; any valid assignment will be accepted.

inputFormat

The first line contains a single integer \(N\), the number of cows. The following \(N\) lines each contain two integers \(A\) and \(B\) representing the start and end time (both inclusive) of the milking session for a cow.

N
A B
A B
... (N lines total)

outputFormat

On the first line, output the minimum number of stalls needed. Then output \(N\) lines, where the \(i\)th line indicates the stall number assigned to the \(i\)th cow (in the same order as the input).

sample

3
1 2
2 3
3 4

2
1
2
1