CF1477C.Nezzar and Nice Beatmap

Nezzar loves the game osu!.

osu! is played on beatmaps, which can be seen as an array consisting of distinct points on a plane. A beatmap is called nice if for any three consecutive points $A,B,C$ listed in order, the angle between these three points, centered at $B$, is strictly less than $90$ degrees.

Points $A,B,C$ on the left have angle less than $90$ degrees, so they can be three consecutive points of a nice beatmap; Points $A',B',C'$ on the right have angle greater or equal to $90$ degrees, so they cannot be three consecutive points of a nice beatmap.

Now Nezzar has a beatmap of $n$ distinct points $A_1,A_2,\ldots,A_n$. Nezzar would like to reorder these $n$ points so that the resulting beatmap is nice.

Formally, you are required to find a permutation $p_1,p_2,\ldots,p_n$ of integers from $1$ to $n$, such that beatmap $A_{p_1},A_{p_2},\ldots,A_{p_n}$ is nice. If it is impossible, you should determine it.

Nezzar 非常喜爱游戏 osu!。

osu! 在“谱面”（beatmap）上进行，而谱面可视为平面上由若干互异点构成的一个数组。若对谱面中任意三个按顺序排列的连续点 $A,B,C$，以 $B$ 为顶点所形成的夹角严格小于 $90^\circ$，则称该谱面是“优美的”（nice）。

左侧的三点 $A,B,C$ 所成夹角小于 $90^\circ$，因此它们可以作为某个优美谱面中三个连续的点；右侧的三点 $A',B',C'$ 所成夹角大于或等于 $90^\circ$，因此它们不能作为任何优美谱面中三个连续的点。

现在 Nezzar 拥有一个包含 $n$ 个互异点 $A_1,A_2,\ldots,A_n$ 的谱面。Nezzar 希望将这 $n$ 个点重新排序，使得所得谱面是优美的。

形式化地说，你需要找出一个 $1$ 到 $n$ 的排列 $p_1,p_2,\ldots,p_n$，使得重排后的谱面 $A_{p_1},A_{p_2},\ldots,A_{p_n}$ 是优美的。若不存在这样的排列，则需判定其不可能性。

The first line contains a single integer $n$ ($3 \le n \le 5000$).

Then $n$ lines follow, $i$-th of them contains two integers $x_i$, $y_i$ ($-10^9 \le x_i, y_i \le 10^9$) — coordinates of point $A_i$.

It is guaranteed that all points are distinct.

第一行包含一个整数 $n$（$3 \le n \le 5000$）。

接下来是 $n$ 行，其中第 $i$ 行包含两个整数 $x_i$、$y_i$（$-10^9 \le x_i, y_i \le 10^9$），表示点 $A_i$ 的坐标。

保证所有点互不相同。

If there is no solution, print $-1$.

Otherwise, print $n$ integers, representing a valid permutation $p$.

If there are multiple possible answers, you can print any.

如果没有解，输出 $-1$。

否则，输出 $n$ 个整数，表示一个合法的排列 $p$。

如果存在多个可能的答案，输出任意一个即可。

Here is the illustration for the first test:

Please note that the angle between $A_1$, $A_2$ and $A_5$, centered at $A_2$, is treated as $0$ degrees. However, angle between $A_1$, $A_5$ and $A_2$, centered at $A_5$, is treated as $180$ degrees.

第一个测试用例的示意图如下：

请注意：以 $A_2$ 为顶点、由 $A_1$、$A_2$ 和 $A_5$ 构成的角被视为 $0^\circ$；而以 $A_5$ 为顶点、由 $A_1$、$A_5$ 和 $A_2$ 构成的角被视为 $180^\circ$。