#from matplotlib import pyplot as plt

def visualize(N,M,pos,center_pos,allocate):
    fig = plt.figure(figsize=(10,10))
    for i in range(N):
        plt.plot(pos[i][0],pos[i][1],color=color_ls[allocate[i]],marker=".")
    for i in range(M):
        plt.plot(center_pos[i][0],center_pos[i][1],color=color_ls[i],marker="*")
    plt.show()
    plt.close()


INF=10**20

import random
from pathlib import Path
import time


LOCAL = False
in_path = "./test"
img_path = "./image"
color_ls = ["red","blue","green","orange","gray","pink","cyan","black"]

def read_data(file):
    if LOCAL:
        with open(file,mode="r") as f:
            data = f.readlines()
        N,M = map(int,data[0].split())
        pos = [[int(x) for x in data[i+1].split()] for i in range(N)]
    else:
        N,M=map(int,input().split())
        pos = [[int(x) for x in input().split()] for i in range(N)]
    return N,M,pos

#2点間の距離を返す 
def dist(p1,p2,a=25): 
    return ((p1[0]-p2[0])**2 + (p1[1]-p2[1])**2) * a

#中心点と各惑星の距離を全探索し、短い順に並びかえる
def calc_dist_from_center(N,M,center_pos,pos):
    dist_list = []
    for m in range(M):
        for n in range(N):
            d = dist(pos[n],center_pos[m])
            dist_list.append((d,m,n))
    return sorted(dist_list)

#中心点から近い惑星順にクラスわけする
def allocate_cluster(N,M,center_pos,pos):
    dist_list = calc_dist_from_center(N,M,center_pos,pos)
    allocate = [-1]*N
    cluster_counts = [0]*M
    total_count = 0
    for d,m,n in dist_list:
        if allocate[n]==-1:
            allocate[n]=m
            cluster_counts[m]+=1
            total_count+=1
        if total_count==N:
            break
    return allocate,cluster_counts
    
#クラスター分けされた点をもとに、k-means法に倣って中心点を算出する。
# グループカウントが多いものは中心点を2つにして、クラスターを分ける。
def calc_center(N,M,pos,allocate,cluster_counts,max_size = 15,split_mode = True):
    point_sums = [[0,0] for _ in range(M)]
    for i in range(N):
        m=allocate[i]
        point_sums[m][0]+=pos[i][0]
        point_sums[m][1]+=pos[i][1]
    center_pos = []

    #clsuter_countが大きい順に見ていき、中心点がM個を超えたら中断する
    if split_mode:
        order = sorted([(cluster_counts[i],i) for i in range(M)],reverse=True)
    else:
        order = [(cluster_counts[i],i) for i in range(M)]
    for _,m in order:  
        if cluster_counts[m]==0:
            center_pos.append([random.randint(0,1000),random.randint(0,1000)])
        else:
            center_pos.append([point_sums[m][0]//cluster_counts[m],point_sums[m][1]//cluster_counts[m]])
            if cluster_counts[m]>=max_size and split_mode:
                x = point_sums[m][0]//cluster_counts[m]
                y = point_sums[m][1]//cluster_counts[m]
                dx = random.randint(-20,20)
                dy = random.randint(-20,20)
                while not (0<=x+dx<=1000 and 0<y+dy<=1000):
                    dx = random.randint(-5,5)
                    dy = random.randint(-5,5)
                center_pos.append([x+dx,y+dy])
        if len(center_pos)==M:
            break

    return center_pos
    
#K-means法に倣って惑星の点をグループ分けする
def clustering(N,M,pos,max_size):
    center_pos = [[random.randint(0,1000),random.randint(0,1000)] for _ in range(M)] #ランダム初期化
    allocate,cluster_counts = allocate_cluster(N,M,center_pos,pos)
    loop = 0

    while True:
        center_pos = calc_center(N,M,pos,allocate,cluster_counts,max_size=max_size)
        allocate,cluster_counts = allocate_cluster(N,M,center_pos,pos)        
        #print(loop,cluster_counts)
        if loop>=20 and max(cluster_counts)<=max_size:
            break
        loop+=1    

    center_pos = calc_center(N,M,pos,allocate,cluster_counts,split_mode=False)
    #visualize(N,M,pos,center_pos,allocate)

    return center_pos,allocate


def f(S,x,n):
    return S*(n+1)+x


#クラスター内にてBitDPでTSPを解く O(n^2*2^n)
def tsp(id_list,pos,center_pos):    
    #point 0~n-1が惑星、nが中心点
    n=len(id_list)-1
    dp = [INF]*(n+1)*(1<<n)
    dp[f(0,n,n)]=0
    for S in range(1<<n):
        for s in range(n+1):
            if dp[f(S,s,n)]==INF:
                continue
            for t in range(n):
                if (S>>t)&1:
                    continue
                S2 = S|(1<<t)
                if s!=n:
                    dp[f(S2,t,n)]=min(dp[f(S,s,n)] + dist(pos[id_list[s]],pos[id_list[t]]),dp[f(S2,t,n)])
                else:
                    dp[f(S2,t,n)]=min(dp[f(S,s,n)] + dist(center_pos,pos[id_list[t]],a=5),dp[f(S2,t,n)])
                dp[f(S2,n,n)]=min(dp[f(S2,t,n)] + dist(center_pos,pos[id_list[t]],a=5),dp[f(S2,n,n)])


    #BitDPから復元            
    path_list = [n]
    state = (1<<n)-1
    now = n
    v = dp[-1]
    e = 10**(-5)
    while state != 0 or now !=n:
        found = False
        if now == n:
            for t in range(n):
                d = dist(center_pos,pos[id_list[t]],a=5)
                if dp[f(state,t,n)]==INF:
                    continue
                if v - dp[f(state,t,n)] >= d - e:
                    path_list.append(t)
                    now = t
                    v -= d
                    found = True
                    break
        else:
            state = state ^ (1<<now)
            for t in range(n+1):
                if dp[f(state,t,n)]==INF:
                    continue
                if t!=n:
                    if not (state>>t)&1:
                        continue
                    d = dist(pos[id_list[now]],pos[id_list[t]])
                else:
                    d = dist(pos[id_list[now]],center_pos,a=5)
                if v - dp[f(state,t,n)] >= d - e:
                    path_list.append(t)
                    now = t
                    v -= d
                    found=True
                    break


    return [id_list[i] for i in path_list]


def tsp_between_space(center_pos):
    n = 8
    dp = [[INF for _ in range(n)] for _ in range(1<<n)]
    dp[0][-1]=0
    for S in range(1<<n):
        for s in range(n):
            if dp[S][s]==INF:
                continue
            for t in range(n):
                if (S>>t)&1:
                    continue
                S2 = S|(1<<t)
                d = dist(center_pos[s],center_pos[t],a=1)
                dp[S2][t]=min(dp[S][s] + d, dp[S2][t])


    #BitDPから復元            
    state = (1<<n)-1
    s = n-1
    path_list = [s]
    v = dp[-1][-1]
    e = 10**(-5)
    while state != 0:
        state ^=(1<<s)
        for t in range(n):
            if not (state>>t)&1:
                continue
            if dp[state][t]==INF:
                continue
            d = dist(center_pos[s],center_pos[t],a=1)
            if v - dp[state][t] >= d - e:
                path_list.append(t)
                s = t
                v -= d
                break
    return path_list        



def adjust_center_pos(path,pos,M):
    L=len(path)
    edge_count = [0]*M
    edge_x_sum = [0]*M
    edge_y_sum = [0]*M
    for i in range(L-1):
        if path[i]<0 and path[i+1]>=0:
            p,q = -path[i]-1,path[i+1]
        elif path[i]>=0 and path[i+1]<0:
            p,q = -path[i+1]-1,path[i]
        else:
            continue
        edge_count[p]+=1
        edge_x_sum[p]+=pos[q][0]
        edge_y_sum[p]+=pos[q][1]
    center_pos = [[edge_x_sum[m]//edge_count[m],edge_y_sum[m]//edge_count[m]] for m in range(M)]
    return center_pos

def calc_score(N,M,path,pos,center_pos):
    score = 0
    L = len(path)
    for i in range(L-1):
        a=1
        if path[i]>=0:
            p1 = pos[path[i]]
            a*=5
        else:
            p1 = center_pos[-path[i]-1]
        if path[i+1]>=0:
            p2 = pos[path[i+1]]
            a*=5
        else:
            p2 = center_pos[-path[i+1]-1]
        score += dist(p1,p2,a)
    return 10**9 / (1000 + score**0.5)
    
    



def main(N,M,pos):
    #K-meansで8個に分割
    center_pos,allocate = clustering(N,M,pos,21)
    ans = []

    #クラスタ間での回る順番をTSPで決める
    space_order = tsp_between_space(center_pos)

    #クラスタ内で回る順番をTSPで決める
    for m in space_order:
        id_list = [i for i in range(N) if allocate[i]==m]
        n = len(id_list)
        #サイズが小さい時は全部使う
        if n<=12:
            ans += tsp(id_list+[-m-1],pos,center_pos[m])

        #サイズが大きすぎる時は、clusteringで2つに分割してそれぞれでTSP
        else:
            pos2 = [pos[i] for i in id_list]
            _,allocate2 = clustering(n,2,pos2,12)
            for i2 in range(2):
                id_list2 = [id_list[i] for i in range(n) if allocate2[i]==i2]
                ans += tsp(id_list2+[-m-1],pos,center_pos[m])

    #初期位置を0にする
    start_point = ans.index(0)
    ans = ans[start_point:]+ans[:start_point+1] #初期解

    #center-posの位置を補正（最小二乗法の要領）
    center_pos = adjust_center_pos(ans,pos,M)

    score = calc_score(N,M,ans,pos,center_pos)
        
    return center_pos,ans,score

def output(center_pos,ans):
    for x,y in center_pos:
        print(x,y)
    print(len(ans))
    for a in ans:
        if a<0:
            print(2,-a)
        else:
            print(1,a+1)

if LOCAL:
    file_ls = Path(in_path).glob("*.txt")
    for file in file_ls:
        print(file)
        N,M,pos = read_data(file)
        center_pos,ans = main(N,M,pos)
        print(ans)
        output(center_pos,ans)
else:
    N,M,pos = read_data("")
    best_score=0
    for _ in range(2):
        center_pos,ans,score = main(N,M,pos)
        if score>best_score:
            best_pos = center_pos
            best_ans = ans
    output(best_pos,best_ans)