問題文

二次元平面上に N 個の都市があり、1 から N までの番号が付けられています。

都市 i は座標 (X_i, Y_i) にあり、都市 i から都市 j までの距離は \sqrt{(X_i-X_j)^2+(Y_i-Y_j)^2} です。

都市 1 から出発し、すべての都市を一度ずつ通った後、都市 1 へ戻ってくる経路のうち、合計距離ができるだけ短いものを出力してください。

制約

• N=150
• 0 \leq X_i, Y_i \leq 1000

入力例 1

7
1 1
4 1
2 5
3 4
3 2
4 2
5 5

出力例 1

1
2
6
7
3
4
5
1

これは説明用のテストケースであり、制約を満たしていない（採点用テストケースに含まれない）ことに注意してください。

入力例 2

150
860 284
397 996
481 973
529 426
257 308
770 955
858 574
268 891
905 659
521 14
290 700
864 329
569 774
152 841
548 670
838 815
912 87
777 360
59 851
594 462
978 711
705 534
757 64
63 53
236 938
91 561
259 626
170 538
999 126
376 591
810 964
526 981
410 798
535 728
395 708
333 856
590 719
375 208
382 790
340 613
340 2
530 351
439 526
2 828
44 459
300 907
31 980
29 26
759 162
437 303
55 787
638 514
53 68
46 114
395 716
71 732
292 844
584 305
521 619
402 821
398 220
55 375
675 399
484 33
178 356
532 929
144 960
793 772
430 865
692 818
431 707
414 674
819 760
527 653
863 698
422 504
762 698
808 479
534 3
423 715
700 125
557 545
20 1000
218 537
75 372
313 985
457 463
365 866
399 477
205 51
484 719
363 766
666 813
307 335
513 208
495 417
140 115
225 731
397 516
665 409
402 430
217 649
446 848
696 307
224 823
177 258
305 3
526 329
654 116
268 160
936 529
228 853
260 866
838 691
53 543
28 32
984 775
889 746
382 91
413 691
595 522
61 667
105 242
258 346
927 794
624 337
995 647
315 102
901 22
858 738
13 692
238 741
388 305
817 307
458 793
486 15
968 875
863 36
967 493
463 539
493 662
910 83
253 343
212 410
564 332
624 77
659 468
945 707
498 227
952 2

出力例 2

1
12
134
18
104
126
58
145
108
42
96
4
20
121
52
147
100
63
22
78
7
111
139
127
21
148
9
75
114
130
118
125
117
137
16
73
68
77
70
93
13
34
91
71
80
120
72
35
55
92
39
33
60
103
69
88
36
57
113
8
46
25
112
105
14
19
44
51
56
122
131
26
115
45
62
85
65
144
143
124
5
94
133
50
61
38
119
128
110
90
97
54
53
24
116
48
123
106
28
84
27
102
98
132
11
40
30
99
76
43
140
87
89
101
82
59
74
15
141
37
135
66
32
3
2
86
67
47
83
6
31
149
95
109
81
49
23
138
129
150
142
17
29
146
79
10
136
64
41
107
1