import sys import numpy as np from scipy.cluster.vq import kmeans2 def tsp(cost): n = cost.shape[0] n2 = 1 << n INF = 1 << 60 dp = np.full((n2, n, 2), INF, np.int64) for i in range(n): dp[1 << i, i] = 0 for i in range(n2): for j in range(n): if ~i >> j & 1: continue for k in range(n): if i >> k & 1: continue l = i | 1 << k d = dp[i, j, 0] + cost[j, k] if d < dp[l, k, 0]: dp[l, k] = d, j res = np.empty(n, np.int64) i = n2 - 1 x = dp[i, :, 0].argmin() for j in range(n): res[j] = x p = dp[i, x, 1] i ^= 1 << x x = p return res def greedy(cost): n = cost.shape[0] res = np.empty(n, np.int64) INF = 1 << 60 d_min = INF visited = np.empty(n, np.bool_) tmp = np.empty(n, np.int64) for x in range(n): visited.fill(False) visited[x] = True tmp[0] = x d = 0 for i in range(1, n): y = np.where(visited, INF, cost[x]).argmin() tmp[i] = y visited[y] = True d += cost[x, y] x = y if d < d_min: res = tmp.copy() return res def main(): np.random.seed(11) N, M = map(int, input().split()) X, Y = np.fromstring(sys.stdin.read(), np.int64, sep=' ').reshape(-1, 2).T C, L = kmeans2(np.vstack((X, Y)).T.astype(np.float64), M, 20, minit='++') C = np.round_(C).astype(np.int64) sb2 = lambda x: np.subtract.outer(x, x) ** 2 dist = lambda x, y: sb2(x) + sb2(y) for i in range(M): print(*C[i]) ans = [[1, 1]] R = tsp(dist(C[:, 0], C[:, 1])) c0 = ((C[:, 0] - X[0]) ** 2 + (C[:, 1] - Y[0]) ** 2).argmin() R = np.roll(R, -(R == c0).nonzero()[0][0]) for i in R: ans.append([2, i + 1]) cx, cy = C[i] idx = L == i V = idx.nonzero()[0] n = V.shape[0] cost = dist(X[idx], Y[idx]) cost0 = (X[idx] - cx) ** 2 + (Y[idx] - cy) ** 2 U = tsp(cost) if n < 12 else greedy(cost) if V[U[0]] == 0: s = 2 u = U[1] else: s = 1 u = U[0] ans.append([1, V[u] + 1]) for nu in U[s:]: if V[nu] == 0: continue if 5 * cost[u, nu] > cost0[u] + cost0[nu]: ans.append([2, i + 1]) ans.append([1, V[nu] + 1]) u = nu ans.append([2, i + 1]) ans.append([2, R[0] + 1]) ans.append([1, 1]) print(len(ans)) for a, b in ans: print(a, b) if __name__ == '__main__': main()