import copy
import random
from time import perf_counter
import argparse
import sys
import math

class TimeKeeper:
    def __init__(self):
        self.start_time = perf_counter()
    def is_time_over(self, LIMIT):
        return (perf_counter() - self.start_time) >= LIMIT
    def time_now(self):
        return (perf_counter() - self.start_time)

def main(DEBUG):
    # ユークリッド距離
    def euclidean_distance(p1, p2):
        return sum((a - b) ** 2 for a, b in zip(p1, p2)) ** 0.5

    # K-meansクラスタリング
    def initialize_centroids(points, k):
        return random.sample(points, k)

    def assign_clusters(points, centroids):
        clusters = []
        for p in points:
            ds = [euclidean_distance(p, c) for c in centroids]
            clusters.append(ds.index(min(ds)))
        return clusters

    def update_centroids(points, clusters, k):
        new_centroids = []
        for i in range(k):
            pts = [points[j] for j in range(len(points)) if clusters[j] == i]
            if pts:
                avg = [sum(dim)/len(pts) for dim in zip(*pts)]
                new_centroids.append(tuple(avg))
        return new_centroids

    def kmeans(points, k, max_iters=100):
        centroids = initialize_centroids(points, k)
        for _ in range(max_iters):
            clusters = assign_clusters(points, centroids)
            new_centroids = update_centroids(points, clusters, k)
            if centroids == new_centroids:
                break
            centroids = new_centroids
        return clusters, centroids

    # Held–Karp TSP
    def HeldKarp(dists):
        N = len(dists)
        dp = [[10**18]*N for _ in range(1<<N)]
        for i in range(N):
            dp[1<<i][i] = dists[0][i]
        for mask in range(1, 1<<N):
            for v in range(N):
                if not (mask & (1<<v)): continue
                for nv in range(N):
                    if (mask & (1<<nv)) or dists[v][nv] < 0: continue
                    dp[mask|(1<<nv)][nv] = min(
                        dp[mask|(1<<nv)][nv],
                        dp[mask][v] + dists[v][nv]
                    )
        tot = dp[(1<<N)-1][0]
        tour = [0]
        mask = (1<<N)-1
        rem = tot
        EPS = 1e-5
        cur = 0
        for _ in range(N-1):
            mask ^= (1<<cur)
            for prev in range(N):
                if prev == cur: continue
                if abs(rem - dp[mask][prev] - dists[prev][cur]) < EPS:
                    rem -= dists[prev][cur]
                    cur = prev
                    tour.append(cur)
                    break
        return tot, tour

    # 移動コストの比較
    def point_edge_decision(p1, p2, station, ALPHA):
        d12 = euclidean_distance(p1, p2)
        d1s = euclidean_distance(p1, station)
        d2s = euclidean_distance(p2, station)
        direct = ALPHA**2 * d12
        via    = ALPHA * (d1s + d2s)
        return (direct, False) if direct <= via else (via, True)

    # スコア計算
    def calscore(stations, tour, ALPHA):
        s = 0
        for (t0,i0),(t1,i1) in zip(tour, tour[1:]):
            i0 -= 1; i1 -= 1
            if t0 == 1:
                x0,y0 = id_to_xy[i0]
            else:
                x0,y0 = stations[i0]
            if t1 == 1:
                x1,y1 = id_to_xy[i1]
            else:
                x1,y1 = stations[i1]
            d2 = (x0-x1)**2 + (y0-y1)**2
            coef = {2:ALPHA**2, 3:ALPHA, 4:1}[t0+t1]
            s += d2 * coef
        return int(10**9 / (1000 + math.sqrt(s)) + 0.5)

    # ツアー構築部を共通化 (固定 labels, stations)
    def build_tour_with_fixed(labels, stations):
        # 各クラスタ点群と座標辞書
        ps = [[] for _ in range(M)]
        for i,(x,y) in enumerate(points):
            ps[labels[i]].append((x,y,i))
            id_to_xy[i] = (x,y)
        # グループ間TSP
        dists = [[euclidean_distance(stations[i], stations[j])
                  for j in range(M)] for i in range(M)]
        _, tour_grp = HeldKarp(dists)

        tour = [(1,1)]
        # 点0 を除外
        ps[0].remove((id_to_xy[0][0], id_to_xy[0][1], 0))

        for grp in tour_grp:
            station = stations[grp]
            tour.append((2, grp+1))
            current = station
            rem = ps[grp].copy()
            while rem:
                best = None
                best_cost = float('inf')
                best_via = False
                for x,y,pid in rem:
                    cost,via = point_edge_decision(current, (x,y), station, ALPHA)
                    if cost < best_cost:
                        best_cost, best = cost, (x,y,pid)
                        best_via = via
                # 経由判定
                if best_via and current != station:
                    tour.append((2, grp+1))
                    current = station
                x,y,pid = best
                tour.append((1, pid+1))
                current = (x,y)
                rem.remove(best)
            if current != station:
                tour.append((2, grp+1))

        tour.append((2,1))
        tour.append((1,1))
        return tour, calscore(stations, tour, ALPHA)

    # solve(): k-means → 回転 → build_tour_with_fixed
    def solve(N, M, ALPHA, points):
        # k-means
        while True:
            labels, cents = kmeans(points, M)
            stations = []
            for x,y in cents:
                stations.append((int(x+0.5), int(y+0.5)))
            if len(stations) == M:
                break
        # スタート回転
        st0 = labels[0]
        labels = [ (c-st0)%M for c in labels ]
        stations = stations[st0:] + stations[:st0]
        # ツアー構築＆スコア
        tour, sc = build_tour_with_fixed(labels, stations)
        return labels, stations, tour, sc

    # ステーション微調整
    def refine_stations(labels, points, stations, ALPHA):
        best_st = stations[:]
        _, tour0, best_sc = None, None, -1
        # 初期評価
        tour0, best_sc = build_tour_with_fixed(labels, best_st)
        improved = True
        deltas = [(-1,0),(1,0),(0,-1),(0,1)]
        while improved:
            improved = False
            for i in range(len(best_st)):
                sx, sy = best_st[i]
                for dx, dy in deltas:
                    cand = best_st[:]
                    cand[i] = (sx+dx, sy+dy)
                    tour_c, sc_c = build_tour_with_fixed(labels, cand)
                    if sc_c > best_sc:
                        best_sc = sc_c
                        tour0   = tour_c
                        best_st = cand
                        improved = True
                        break
                if improved:
                    break
        return best_st, tour0, best_sc

    # ------------ main loop ------------
    tk = TimeKeeper()
    LIMIT = 0.8
    random.seed(0)
    ALPHA = 5

    # 入力
    N, M = map(int, input().split())
    points = [tuple(map(int, input().split())) for _ in range(N)]
    # グローバル辞書初期化
    id_to_xy = {}

    best_sc = -1
    best_labels = best_stations = best_tour = None
    loop = 0
    while not tk.is_time_over(LIMIT):
        labels, stations, tour, sc = solve(N, M, ALPHA, points)
        if sc > best_sc:
            best_sc = sc
            best_labels, best_stations, best_tour = labels, stations, tour
        loop += 1

    # ステーション微調整
    best_stations, best_tour, best_sc = refine_stations(
        best_labels, points, best_stations, ALPHA
    )

    # 出力
    print('SC', best_sc, file=sys.stderr)
    for x,y in best_stations:
        print(x, y)
    print(len(best_tour))
    for t,i in best_tour:
        print(t, i)


if __name__ == '__main__':
    parser = argparse.ArgumentParser(description='Debug mode')
    parser.add_argument('--debug', action='store_true', help='Enable debug mode')
    args = parser.parse_args()
    main(args.debug)