AT_abc448_f [ABC448F] Authentic Traveling Salesman Problem

There are $ N $ locations numbered $ 1 $ to $ N $ on a two-dimensional plane. Location $ i $ is at coordinates $ (X_i, Y_i) $ . You will start from location $ 1 $ , visit every location exactly once, and return to location $ 1 $ . Moving from location $ i $ to location $ j $ takes $ \vert X_i - X_j \vert + \vert Y_i - Y_j \vert $ seconds. Output a route that visits all locations and returns to location $ 1 $ within $ 10^{10} $ seconds of starting from location $ 1 $ . It is guaranteed that at least one such route exists under the given constraints.

The input is given from Standard Input in the following format: > $ N $ $ X_1 $ $ Y_1 $ $ X_2 $ $ Y_2 $ $ \vdots $ $ X_N $ $ Y_N $

Let $ p_i $ be the $ i $ -th location visited $ (1 \leq i \leq N) $ , and output your answer in the following format. > $ p_1 $ $ p_2 $ $ \dots $ $ p_N $ Your answer is considered correct if all of the following conditions are satisfied. - $ (p_1, p_2, \dots, p_N) $ is a permutation of $ (1, 2, \dots, N) $ . - $ p_1 = 1 $ - Letting $ d(i, j) $ be the number of seconds it takes to move from location $ i $ to location $ j $ , $ \displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1} ) \leq 10^{10} $ . If there are multiple valid answers, any of them will be accepted.

### Sample Explanation 1 $ \displaystyle \sum_{i=1}^N d(p_i, p_{(i \bmod N) + 1}) = 4 + 2 + 4 = 10 $ , so the output satisfies the condition. ### Constraints - $ 1 \leq N \leq 6 \times 10^4 $ - $ 0 \leq X_i \leq 2 \times 10^7 $ - $ 0 \leq Y_i \leq 2 \times 10^7 $ - $ (X_i, Y_i) \neq (X_j, Y_j) $ if $ i \neq j $ - All input values are integers.