from itertools import permutations import sys import random import time input = lambda: sys.stdin.readline().rstrip() random.seed(0) start = time.time() N, M = map(int, input().split()) AB = [list(map(int, input().split())) for _ in range(N)] def fit(X): labels_ = [] now = 0 while len(labels_) < len(X): labels_.append(now) now += 1 if now == 8: now = 0 random.shuffle(labels_) labels_prev = [0]*len(X) count = 0 cluster_centers_ = [(0, 0) for _ in range(8)] while count < 1000: syuukei = [[] for _ in range(8)] for i in range(len(X)): syuukei[labels_[i]].append(X[i]) for i,l in enumerate(syuukei): if l: x, y = sum(x for x,y in l)//len(l), sum(y for x,y in l)//len(l) else: x, y = random.randint(0, 1000), random.randint(0, 1000) cluster_centers_[i] = (x, y) labels_prev = labels_[:] for i in range(len(X)): dist = 10**18 for j in range(8): tmp = (X[i][0] - cluster_centers_[j][0])**2 + (X[i][1] - cluster_centers_[j][1])**2 if tmp < dist: dist = tmp labels_[i] = j count += 1 return labels_, cluster_centers_ def main(): labels, centers = fit(AB) def dist(a, b): return (a[0] - b[0])**2 + (a[1] - b[1])**2 ANS = [] L = [[] for _ in range(8)] for i, cluster_number in enumerate(labels): L[cluster_number].append(i) vest_p = None vest = 1<<30 for p in permutations(range(8)): score = dist((AB[0]), centers[p[0]]) for i in range(len(centers)-1): score += dist(centers[p[i]], centers[p[i+1]]) score += dist(centers[p[-1]], AB[0]) if score < vest: vest = score vest_p = p[:] if time.time() - start > 0.9: return 1<<30, -1, -1 ans = [(1, 0)] for i in vest_p: if i >= len(L): continue ans.append((2, i)) lim = len(L[i]) j = 0 while j < lim: d1 = 5 * dist(AB[L[i][j]], centers[i]) d2 = 1<<30 if j+1 < len(L[i]): d2 = 25* dist(AB[L[i][j]], AB[L[i][j+1]]) if d2 < d1: ans.append((1, L[i][j])) else: ans.append((1, L[i][j])) ans.append((2, i)) j += 1 ans.append((1, 0)) score = 0 for i in range(len(ans)-1): type_pre, indx_pre = ans[i] type_now, indx_now = ans[i+1] if type_pre == 1 and type_now == 1: score += 25*dist(AB[indx_pre], AB[indx_now]) elif type_pre == 1 and type_now == 2: score += 5*dist(AB[indx_pre], centers[indx_now]) elif type_pre == 2 and type_now == 1: score += 5*dist(centers[indx_pre], AB[indx_now]) elif type_pre == 2 and type_now == 2: score += dist(centers[indx_pre], centers[indx_now]) return score, ans, centers ANS = [] CENTERS = [] vest = 1<<30 cnt = 0 while time.time() - start < 0.8: cnt += 1 tmp, ans, centers = main() if tmp < vest: vest = tmp ANS = ans[:] CENTERS = centers print(round(10**9 / (1000 + vest**.5)), file=sys.stderr) print(cnt, file=sys.stderr) for c,d in CENTERS: print(c, d) print(len(ANS)) for a,b in ANS: print(a, b+1)