from time import time start_time = time() import sys import io import os input = sys.stdin.readline import random, math random.seed(42) alpha = 5 mx = 1000 INF = float('inf') Ts = 50 Te = 10 TIME_LIMIT = 0.9 limit = 700 n, m = map(int, input().split()) XY = [] for i in range(n): x, y = map(int, input().split()) XY.append((x, y)) CD = [] for i in range(m): c = random.randint(0, mx) d = random.randint(0, mx) CD.append((c, d)) XY += CD def calc_energy(i, j): xi, yi = XY[i] xj, yj = XY[j] d2 = (xi-xj)**2+(yi-yj)**2 if 0 <= i < n and 0 <= j < n: return (alpha**2)*d2 elif n <= i < n+m and n <= j < n+m: return d2 else: return alpha*d2 g = [[] for i in range(n+m)] dist_table = [[INF]*(n+m) for i in range(n+m)] for i in range(n+m): for j in range(n+m): if i == j: continue x1, y1 = XY[j] dist = calc_energy(i, j) g[i].append((dist, j)) dist_table[i][j] = dist def calc_dist(path, dist_table): res = 0 for v, nv in zip(path, path[1:]): res += dist_table[v][nv] return res def nearest_neighbor(s, g): n = len(g) nonvisit = set(range(n)) path = [] path.append(s) nonvisit.remove(s) while nonvisit: min_dist = INF nx = -1 for d, v in g[path[-1]]: if not v in nonvisit: continue if d < min_dist: min_dist = d nx = v path.append(nx) nonvisit.remove(nx) return path+[s] def two_opt_with_annealing(path, dist_table, Ts, Te, time_limit): n = len(path) while True: now_time = time() if now_time - start_time > time_limit: return path for i in range(n-3): p1 = path[i] p2 = path[i+1] p_dist = dist_table[p1][p2] for j in range(i+2, n-1): q1 = path[j] q2 = path[j+1] q_dist = dist_table[q1][q2] cur_dist = p_dist + q_dist new_dist = dist_table[p1][q1]+dist_table[p2][q2] diff = new_dist-cur_dist temp = Ts+(Te-Ts)*(time()-start_time)/time_limit prob = math.exp(min(limit, -diff / temp)) if prob > random.random(): sep1, sep2, sep3 = path[:i+1], path[i+1:j+1], path[j+1:] sep2.reverse() path = sep1+sep2+sep3 path = nearest_neighbor(0, g) path = two_opt_with_annealing(path, dist_table, Ts, Te, TIME_LIMIT) s = calc_dist(path, dist_table) score = round(10**9/(1000+math.sqrt(s))) print(score, file=sys.stderr, flush=True) for c, d in CD: print(c, d) print(len(path)) for k in range(len(path)): r = path[k] if 0 <= r < n: print(1, r+1) else: print(2, r-n+1)