"""Nearest neighbour, then 2-opt until no exchange of two edges shortens the tour.""" import json import math import sys p = json.load(sys.stdin) n = len(p) def d(i, j): return math.dist(p[i], p[j]) left, tour = set(range(1, n)), [0] while left: nxt = min(left, key=lambda j: d(tour[-1], j)) left.remove(nxt) tour.append(nxt) better = True while better: better = False for i in range(1, n - 1): for j in range(i + 1, n): a, b, c, e = tour[i - 1], tour[i], tour[j], tour[(j + 1) % n] if d(a, c) + d(b, e) < d(a, b) + d(c, e) - 1e-12: tour[i:j + 1] = reversed(tour[i:j + 1]) better = True print(json.dumps(tour))