Minimize the Maximum Value in an Infinite Sequence

We have an infinite sequence \(A\) (indexed by all integers) initially filled with zeros. You are given \(n\) intervals \( [l_i, r_i] \) (with \(l_i \le r_i\)) for \(i=1,2,\dots,n\). For each interval you must perform exactly one of the following operations (choose one per interval):

1. For every integer \(j \in [l_i,r_i]\), update \(A_j \gets A_j+1\).
2. For every integer \(j \notin [l_i,r_i]\), update \(A_j \gets A_j+1\).

After performing one operation for each interval, the sequence \(A\) is updated. Notice that for any given interval, the effect is localized if you choose operation 1 (only the indices inside the interval are incremented) and global if you choose operation 2 (all indices outside the interval are incremented).

Your task is to decide, for each interval, which operation to use so that the maximum value in \(A\) is minimized. In other words, if we define for every integer \(j\):

[ f(j)=\sum_{i=1}^n\Bigl(\mathbf{1}{{j\in [l_i,r_i]}}\cdot \mathbf{1}{{\text{choose op1 for }i}} + \mathbf{1}{{j\notin [l_i,r_i]}}\cdot \mathbf{1}{{\text{choose op2 for }i}}\Bigr), ]

find a choice of operations for the \(n\) intervals so that \(\max_{j\in\mathbb{Z}}f(j)\) is as small as possible, and output that minimum possible maximum value along with a corresponding plan.

Note. The intervals are finite even though the sequence is infinite. Hence, for any plan the effect is “localized” in the union of intervals (where some intervals add when using op1) and “global” outside the intervals (where an op2 always adds 1). In particular, if an index \(j\) is not covered by any interval then its final value is exactly the number of intervals on which operation 2 was chosen.

Hint. If you denote by \(T_1\) the set of indices for which you choose op1 and \(T_2\) those for op2 (with \(|T_1|+|T_2|=n\)), then for any integer \(j\) the final value is \[ f(j)=\bigl(|T_2|\bigr)+\Bigl(\#\{i\in T_1: j\in [l_i,r_i]\}\Bigr) - \Bigl(\#\{i\in T_2: j\in [l_i,r_i]\}\Bigr). \] A key idea is to try to “balance” the contributions so that no index gets too many increments.

inputFormat

The first line contains a single integer \(n\) (the number of intervals; you may assume \(n\) is small, e.g. \(n \le 20\)). Each of the following \(n\) lines contains two integers \(l_i\) and \(r_i\) (with \(l_i \le r_i\)), representing an interval \([l_i, r_i]\). All \(l_i, r_i\) are 32‐bit signed integers.

outputFormat

On the first line output a single integer: the minimum possible maximum value in \(A\) after performing your chosen operations. On the second line output \(n\) numbers. The \(i\)th number should be 1 if you choose to add 1 only within the interval \([l_i,r_i]\) (operation 1) or 2 if you choose to add 1 to every position outside \([l_i,r_i]\) (operation 2).

If there are multiple valid answers, print any.

sample

1
1 3

1
2