CF1192A Building Skyscrapers

我们要建造一个新的城市：Metropolis。它要建在一个无限大的平面直角坐标系中。建好的城市中应该有 $n$ 座摩天大楼，并且它们所占的（平面直角坐标系中的最小）网格互不相同。在建造的任何时间内，我们定义其上没有摩天大楼的网格**为空**。 给定这 $n$ 座摩天大楼的坐标，请你找出**同时满足下列条件**的建造方法： - 工程队只有一台起重机，所以同一时刻**最多只能建造一栋楼**。 - 你可以任意指定第一个建造的楼。 - 后建的楼必须与之前建的楼**共一个边或角**。 - 整个建造过程中，必须有一条路径从城外通向正在建造的楼。路径只能经过**空网格**，且只能从一个网格连向**边相邻**的网格。 如果有解，令建造顺序为 $s_1,...,s_n$，其中每一个元素为对应的大楼**编号**。共有两种类别的任务： 1. 你可以输出任何解。 2. 输出令 $s_n,...,s_1$ 这个序列字典序最大的解。 接下来 $n$ 行每行两个整数 $r_i,c_i\in[-10^9,10^9]$，分别为**编号为 $i$ **的摩天大楼所在网格的横坐标和纵坐标。

无

无

In the first example, there are three skyscrapers in a row. All of them can always be reached from outside the Metropolis, and there are four build orders which preserve connectivity: - 1, 2, 3 - 2, 1, 3 - 2, 3, 1 - 3, 2, 1 Since $ t = 2 $ , we must choose the first option. In the second example, the only difference from the first example is that skyscraper 2 shares only corners with skyscrapers 1 and 3, the same set of orders as in the first sample is valid. Since $ t = 1 $ , each of these answers is correct. In the third example, the Metropolis is disconnected. We obviously can't build that.