Lecture Scheduling

You are given n historical events. The i-th event lasted for a time interval \([a_i, b_i]\). Two events are said to be related if their intervals have a common point, i.e. if they intersect. It is desired to schedule a series of lectures on these events (one lecture per event) satisfying the following conditions:

1. Closeness for related events: For any two events that are related (their intervals intersect), their lecture positions should be at most k apart. Here if lecture positions are numbered 0,1,...,n-1 then for related events with positions i and j we require \(|i-j| \le k\).
2. Chronological order for unrelated events: If two events are not related (their intervals do not intersect) and event A precedes event B in time (i.e. \(b_A < a_B\)), then the lecture on event A must be scheduled before the lecture on event B.

Your task is to determine two things: the minimum integer \(k\ge 0\) for which there exists an ordering of the lectures satisfying the above conditions, and one such valid ordering (i.e. a permutation of the events identified by their 1-based indices).

Note: Two intervals \([a_i, b_i]\) and \([a_j, b_j]\) are considered to intersect if \(a_i \le b_j\) and \(a_j \le b_i\), and are considered unrelated if \(b_i < a_j\) or \(b_j < a_i\).

The problem guarantees that the number of events is small (for example, \(n \le 10\)), so that an algorithm which explores all valid orders via backtracking is feasible.

inputFormat

The first line contains an integer \(n\) denoting the number of events.

Then follow \(n\) lines. The \(i\)-th line contains two integers \(a_i\) and \(b_i\) (with \(a_i \le b_i\)), representing the starting and ending times of the \(i\)-th event.

Events are numbered from 1 to \(n\) in the order of input.

outputFormat

Output two lines:

• The first line contains the minimum integer \(k\) such that there is an ordering satisfying the required conditions.
• The second line contains a valid ordering – a permutation of the numbers from 1 to \(n\) (separated by spaces) representing the lecture order.

sample

3
1 3
2 5
4 6

1
1 2 3