Authentic Traveling Salesman Problem

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

二维平面上有 $N$ 个地点，编号为 $1$ 到 $N$。地点 $i$ 的坐标为 $(X_i,Y_i)$。

你要从地点 $1$ 出发，恰好访问每个地点一次，最后回到地点 $1$。从地点 $i$ 移动到地点 $j$ 需要 $|X_i-X_j|+|Y_i-Y_j|$ 秒。

请输出一条路线，使得从地点 $1$ 出发、访问所有地点并回到地点 $1$ 的总用时不超过 $10^{10}$ 秒。题目保证在给定约束下至少存在一条满足条件的路线。

输入格式

输入由标准输入给出，格式如下：

$$\begin{aligned} &N\\ &X_1\ Y_1\\ &X_2\ Y_2\\ &\vdots\\ &X_N\ Y_N \end{aligned}$$

输出格式

设第 $i$ 个访问的地点为 $p_i$，输出 $p_1,p_2,\ldots,p_N$。输出必须满足：

• $(p_1,p_2,\dots,p_N)$ 是 $(1,2,\dots,N)$ 的一个排列；
• $p_1=1$；
• 记 $d(i,j)=|X_i-X_j|+|Y_i-Y_j|$，则 $\displaystyle\sum_{i=1}^{N}d\bigl(p_i,p_{(i\bmod N)+1}\bigr)\le10^{10}$。

若有多个合法答案，输出任意一个即可。

样例输入 1

3
0 6
3 5
2 4

样例输出 1

1 3 2

样例输入 2

10
9706344 19786176
19341349 15565412
5711023 19068083
12521132 14054301
14767612 17088029
14961700 18526945
13801766 5740101
6581153 8643675
13176196 16586661
4086263 5172719

样例输出 2

1 5 2 6 4 7 9 8 3 10

数据范围

• $1\le N\le6\times10^4$；
• $0\le X_i,Y_i\le2\times10^7$；
• 所有地点坐标两两不同；
• 所有输入值均为整数。

子任务编号	分值	特殊限制
1	20	$N\le250$
2	40	$N\le498$
3		无特殊限制