static mut XORSHIFT1: u128 = 123456789;
static mut XORSHIFT2: u128 = 362436069;
static mut XORSHIFT3: u128 = 521288629;
static mut XORSHIFT4: u128 = 88675123;
fn xorshift() -> u128 {
    unsafe {
        let mut t = 0;
        t = XORSHIFT1 ^ (XORSHIFT1 << 11u128);
        XORSHIFT1 = XORSHIFT2;
        XORSHIFT2 = XORSHIFT3;
        XORSHIFT3 = XORSHIFT4;
        XORSHIFT4 = (XORSHIFT4 ^ (XORSHIFT4 >> 19u128)) ^ (t ^ (t >> 8u128));
        t
    }
}
pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0;
    let t = std::time::SystemTime::now()
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    unsafe {
        if STIME < 0.0 {
            STIME = ms;
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 2.0
        }
        #[cfg(not(feature = "local"))]
        {
            (ms - STIME)
        }
    }
}

fn read_input() -> (usize, usize, Vec<(i32, i32)>) {
    let (n, m) = {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_end().to_owned();
        let mut ws = s.split_whitespace();
        let n: usize = ws.next().unwrap().parse().unwrap();
        let m: usize = ws.next().unwrap().parse().unwrap();
        (n, m)
    };
    let mut xy = vec![];
    for _ in 0..n {
        let mut s = String::new();
        std::io::stdin().read_line(&mut s).unwrap();
        let s = s.trim_end().to_owned();
        let mut ws = s.split_whitespace();
        let a: i32 = ws.next().unwrap().parse().unwrap();
        let b: i32 = ws.next().unwrap().parse().unwrap();
        xy.push((a, b));
    }
    (n, m, xy)
}
const MAX_X: i32 = 1000;
type Point = (i32, i32);

// fn dist(p: &Point, q: &Point) -> i32 {
//     (((p.0 - q.0) * (p.0 - q.0) + (p.1 - q.1) * (p.1 - q.1)) as f64).sqrt() as i32
// }
fn dist_powered(p: &Point, q: &Point) -> i32 {
    (p.0 - q.0) * (p.0 - q.0) + (p.1 - q.1) * (p.1 - q.1)
}
fn kmeans(points: &[Point], k: usize, max_iter: usize) -> (Vec<Point>, Vec<usize>) {
    let n = points.len();
    let mut centors = Vec::with_capacity(k);
    for _ in 0..k {
        centors.push((
            (xorshift() as i32).abs() % (MAX_X + 1),
            (xorshift() as i32).abs() % (MAX_X + 1),
        ));
    }
    let mut cluster_ids = vec![0; n];
    let mut cluster_sizes = vec![0; k];
    cluster_sizes[0] = n as i32;

    let mut updated = false;
    for loop_count in 0..max_iter {
        // 各点から最も近い代表点を探す
        for i in 0..n {
            let mut nearest_centor_id = 0;
            let mut nearest_centor_distance = dist_powered(&points[i], &centors[0]);
            for j in 1..k {
                let distance = dist_powered(&points[i], &centors[j]);
                if distance < nearest_centor_distance {
                    nearest_centor_distance = distance;
                    nearest_centor_id = j;
                }
            }
            if nearest_centor_id != cluster_ids[i] {
                cluster_sizes[cluster_ids[i]] -= 1;
                cluster_ids[i] = nearest_centor_id;
                cluster_sizes[nearest_centor_id] += 1;
                updated = true;
            }
        }
        // 代表点の座標をクラスタの中心に移動する
        let mut dxs = vec![0; k];
        let mut dys = vec![0; k];
        for i in 0..n {
            let cid = cluster_ids[i];
            dxs[cid] += points[i].0 - centors[cid].0;
            dys[cid] += points[i].1 - centors[cid].1;
        }
        for i in 0..k {
            if cluster_sizes[i] == 0 {
                continue;
            }
            centors[i].0 += dxs[i] / cluster_sizes[i];
            centors[i].1 += dys[i] / cluster_sizes[i];
        }
        if !updated {
            eprintln!("kmeans loop breaked at loop {}", loop_count);
            break;
        }
    }
    (centors, cluster_ids)
}

// fn tsp_dp(points:&[Point])->Vec<usize>{
//     let n = points.len();
//     let mut dp = vec![]

// }

const ALPHA: i32 = 5;
fn get_cost_coefficient(t1: usize, t2: usize) -> i32 {
    if t1 == PLANET {
        if t2 == PLANET {
            ALPHA * ALPHA
        } else {
            ALPHA
        }
    } else {
        if t2 == PLANET {
            ALPHA
        } else {
            1
        }
    }
}

const PLANET: usize = 1;
const STATION: usize = 2;
fn search_path(
    stations: &[Point],
    planets: &[Point],
    cluster_ids: &[usize],
) -> Vec<(usize, usize)> {
    let n = planets.len();
    let m = stations.len();

    // 全点対の最短経路を求める
    let mut next = vec![vec![0; n + m]; n + m];
    for i in 0..n + m {
        for j in 0..n + m {
            next[i][j] = j;
        }
    }
    let mut dist = vec![vec![i32::MAX / 4; n + m]; n + m];
    for i in 0..n + m {
        let p = if i < n { planets[i] } else { stations[i - n] };
        let tp = if i < n { PLANET } else { STATION };
        for j in 0..n + m {
            let q = if j < n { planets[j] } else { stations[j - n] };
            let tq = if i < n { PLANET } else { STATION };
            dist[i][j] = get_cost_coefficient(tp, tq) * dist_powered(&p, &q);
        }
    }
    for k in 0..n + m {
        for i in 0..n + m {
            for j in 0..n + m {
                if dist[i][k] + dist[k][j] < dist[i][j] {
                    dist[i][j] = dist[i][k] + dist[k][j];
                    next[i][j] = next[i][k];
                }
            }
        }
    }

    // 経路を作成する
    let mut path = vec![(PLANET, 0)];
    let mut visited = vec![false; planets.len()];
    visited[0] = true;
    let mut count_visited_planets = 1;

    let mut cur_id = 0;

    while count_visited_planets < planets.len() {
        // まだ到達していない惑星のなかで距離が最小のものに移動する
        let mut nearest_distance = i32::MAX;
        let mut nearest = (PLANET, 0);
        for i in 0..planets.len() {
            if visited[i] {
                continue;
            }
            // let distance =
            //     get_cost_coefficient(cur_type, PLANET) * dist_powered(&cur_point, &planets[i]);
            if dist[cur_id][i] < nearest_distance {
                nearest_distance = dist[cur_id][i];
                nearest = (PLANET, i);
            }
        }

        // 経路に追加する
        if nearest.0 == PLANET {
            count_visited_planets += 1;
            visited[nearest.1] = true;

            // 経路復元
            let mut cur = cur_id;
            while cur != nearest.1 {
                cur = next[cur][nearest.1];
                path.push((if cur < n { PLANET } else { STATION }, cur % n));
            }
        }
        path.push(nearest);
        cur_id = nearest.1;
    }

    // planet0に帰る
    let mut cur = cur_id;
    while cur != 0 {
        cur = next[cur][0];
        path.push((if cur < n { PLANET } else { STATION }, cur % n));
    }

    let path_len = path.len();
    fn get_cost(
        planets: &[Point],
        stations: &[Point],
        a: (usize, usize),
        b: (usize, usize),
    ) -> i32 {
        get_cost_coefficient(a.0, b.0)
            * dist_powered(
                if a.0 == PLANET {
                    &planets[a.1]
                } else {
                    &stations[a.1]
                },
                if b.0 == PLANET {
                    &planets[b.1]
                } else {
                    &stations[b.1]
                },
            )
    }
    // 2-opt
    while get_time() < 0.95 {
        let i = xorshift() as usize % (path_len - 3);
        let j = xorshift() as usize % (path_len - i - 2) + i;
        let a = path[i];
        let b = path[i + 1];
        let c = path[j];
        let d = path[j + 1];

        let origi_dist = get_cost(planets, stations, a, b) + get_cost(planets, stations, c, d);
        let new_dist = get_cost(planets, stations, a, c) + get_cost(planets, stations, b, d);
        if new_dist < origi_dist {
            // -a-b-...-c-d-経路を-a-c-...-b-d-の順になるように入れ替える
            let mut head = i + 1;
            let mut tail = j;
            while head < tail {
                path.swap(head, tail);
                head += 1;
                tail -= 1;
            }
        }
    }
    path
}
fn main() {
    let _ = get_time();
    let (n, m, planets) = read_input();
    let (stations, cluster_ids) = kmeans(&planets, m, 1000);
    eprintln!("stations: {:?}", stations);
    let path = search_path(&stations, &planets, &cluster_ids);
    assert!(path.len() <= 100000);

    for (x, y) in stations.iter() {
        println!("{} {}", x, y);
    }
    println!("{}", path.len());
    for (t, i) in path.iter() {
        println!("{} {}", t, i + 1);
    }
}

#[cfg(test)]
mod tests {
    use super::*;
    #[test]
    fn test_kmeans() {
        let points = vec![(10, 10), (1000, 1000), (10, 5), (10, 6)];
        let (centors, cluster_id) = kmeans(&points, 2, 100);
        eprintln!("centors:{:?}", centors);
        eprintln!("cluster_id:{:?}", cluster_id);
        assert_eq!(cluster_id[0], cluster_id[2]);
        assert_eq!(cluster_id[0], cluster_id[3]);
        assert_eq!(centors[cluster_id[0]], (10, 7));
        assert_eq!(centors[cluster_id[1]], (1000, 1000));
    }
}