CF309E.Sheep

Information technologies are developing and are increasingly penetrating into all spheres of human activity. Incredible as it is, the most modern technology are used in farming!

A large farm has a meadow with grazing sheep. Overall there are n sheep and each of them contains a unique number from 1 to n — because the sheep need to be distinguished and you need to remember information about each one, and they are so much alike! The meadow consists of infinite number of regions numbered from 1 to infinity. It's known that sheep i likes regions from l__i to r__i.

There are two shepherds taking care of the sheep: First and Second. First wakes up early in the morning and leads the sheep graze on the lawn. Second comes in the evening and collects all the sheep.

One morning, First woke up a little later than usual, and had no time to lead the sheep graze on the lawn. So he tied together every two sheep if there is a region they both like. First thought that it would be better — Second would have less work in the evening, because sheep won't scatter too much, being tied to each other!

In the evening Second came on the lawn, gathered the sheep and tried to line them up in a row. But try as he might, the sheep wouldn't line up as Second want! Second had neither the strength nor the ability to untie the sheep so he left them as they are, but with one condition: he wanted to line up the sheep so that the maximum distance between two tied sheep was as small as possible. The distance between the sheep is the number of sheep in the ranks that are between these two.

Help Second find the right arrangement.

信息技术正在不断发展，并日益渗透到人类活动的各个领域。令人难以置信的是，最前沿的技术如今也被应用于农业生产中！

一座大型农场拥有一片供绵羊放牧的草地。草地上共有 $n$ 只绵羊，每只绵羊均被赋予一个从 $1$ 到 $n$ 的唯一编号——这是因为绵羊彼此极为相似，必须加以区分，且需要对每一只都记录相关信息！草地由无限多个区域组成，区域编号从 $1$ 开始直至无穷大。已知第 $i$ 只绵羊喜欢的区域范围为 $[l_i, r_i]$（即从 $l_i$ 到 $r_i$ 的所有整数区域）。

有两位牧羊人负责照看这些绵羊：第一位（First）和第二位（Second）。每天清晨，First 起床并带领绵羊到草地上放牧；而 Second 则于傍晚来到草地，将所有绵羊收拢带回。

某天清晨，First 比平时稍晚醒来，来不及带领绵羊放牧。于是他将任意两只存在共同喜爱区域的绵羊用绳子绑在了一起。First 认为这样更好——到了傍晚，Second 的工作量会减轻，因为被绑在一起的绵羊不会散开得太远！

傍晚时分，Second 来到草地，收拢全部绵羊，并试图将它们排成一列。但他无论如何努力，绵羊都无法按 Second 所期望的方式排好队！Second 既没有力气也没有办法解开绳子，因此只得接受现状，但提出了一个条件：他希望将绵羊排成一列，使得任意一对被绳子绑在一起的绵羊之间距离的最大值尽可能小。此处，“距离”定义为这两只绵羊在队列中中间所夹的绵羊数量（即若两只绵羊在队列中的位置分别为 $i$ 和 $j$，则距离为 $|i - j| - 1$）。

请帮助 Second 找出满足该条件的最优排列方案。

The first input line contains one integer n (1 ≤ n ≤ 2000). Each of the following n lines contains two integers l__i and r__i (1 ≤ l__i, r__i ≤ 109; l__i ≤ r__i).

第一行输入包含一个整数 $n$（$1 \leq n \leq 2000$）。接下来的 $n$ 行中，每行包含两个整数 $l_i$ 和 $r_i$（$1 \leq l_i, r_i \leq 10^9$；$l_i \leq r_i$）。

In the single output line print n space-separated numbers — the sought arrangement of the sheep. The i-th value in the line must represent the number of the sheep that took the i-th place from left in the optimal arrangement line.

If there are multiple optimal arrangements, print any of them.

在单行输出中打印 n 个以空格分隔的数字——即所求的绵羊排列。该行中第 i 个数值表示在最优排列中从左往右数第 i 个位置上的绵羊编号。

若存在多个最优排列，输出其中任意一个即可。