//rand

struct Rng {
    seed: usize,
}

impl Rng {
    pub fn new(seed: usize) -> Rng {
        Rng { seed }
    }

    pub fn next(&mut self) {
        self.seed ^= self.seed << 13;
        self.seed ^= self.seed >> 15;
        self.seed ^= self.seed << 17;
    }
    pub fn gen_range(&mut self, a: usize, b: usize) -> usize {
        self.next();
        self.seed % (b - a) + a
    }
}

//proconio
macro_rules! input {
    (source = $s:expr, $($r:tt)*) => {
        let mut iter = $s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
    ($($r:tt)*) => {
        let mut s = {
            use std::io::Read;
            let mut s = String::new();
            std::io::stdin().read_to_string(&mut s).unwrap();
            s
        };
        let mut iter = s.split_whitespace();
        input_inner!{iter, $($r)*}
    };
}

macro_rules! input_inner {
    ($iter:expr) => {};
    ($iter:expr, ) => {};

    ($iter:expr, $var:ident : $t:tt $($r:tt)*) => {
        let $var = read_value!($iter, $t);
        input_inner!{$iter $($r)*}
    };
}

macro_rules! read_value {
    ($iter:expr, ( $($t:tt),* )) => {
        ( $(read_value!($iter, $t)),* )
    };

    ($iter:expr, [ $t:tt ; $len:expr ]) => {
        (0..$len).map(|_| read_value!($iter, $t)).collect::<Vec<_>>()
    };

    ($iter:expr, chars) => {
        read_value!($iter, String).chars().collect::<Vec<char>>()
    };

    ($iter:expr, usize1) => {
        read_value!($iter, usize) - 1
    };

    ($iter:expr, $t:ty) => {
        $iter.next().unwrap().parse::<$t>().expect("Parse error")
    };
}

const TIMELIMIT: f64 = 0.9;
const ALPHA: i64 = 5;
const RATIO: f64 = 0.99;
struct Input {
    n: usize,
    m: usize,
    AB: Vec<(i32, i32)>,
}

impl Input {
    fn new(n: usize, m: usize, AB: Vec<(i32, i32)>) -> Input {
        Input { n, m, AB }
    }
}

struct State {
    labels: Vec<usize>,

    score: usize,
}

fn calcscore(inp: &Input, ans: &Vec<(usize, usize)>, dist: &Vec<Vec<i128>>) -> i128 {
    let mut res = 0_i128;
    for i in 0..ans.len() - 1 {
        let (type1, mut idx1) = ans[i];
        let (type2, mut idx2) = ans[i + 1];
        if type1 == 2 {
            idx1 += inp.n;
        }
        if type2 == 2 {
            idx2 += inp.n;
        }
        res += dist[idx1][idx2];
    }
    res
}

// fn debug(inp: &Input) {
//     for i in 0..inp.m {
//         println!("{} {}", i, i);
//     }
//     let v = 101;
//     println!("{}", v);
//     for i in 0..inp.n {
//         println!("{} {}", 1, i + 1);
//     }
//     println!("{} {}", 1, 1);
// }

fn calcdist(x: i32, y: i32, xx: i32, yy: i32) -> i128 {
    (x as i128 - xx as i128) * (x as i128 - xx as i128)
        + (y as i128 - yy as i128) * (y as i128 - yy as i128)
}
fn calcdistf(x: f64, y: f64, xx: f64, yy: f64) -> f64 {
    (x - xx) * (x - xx) + (y - yy) * (y - yy)
}
fn kmeans(inp: &Input, n_class: usize, ratio: f64) -> (Vec<usize>, Vec<(i32, i32)>) {
    let mut res_label: Vec<usize> = (0..inp.n).map(|x| x % n_class).collect();
    let mut is_update = true;
    let mut res_g = Vec::new();

    while is_update {
        is_update = false;

        let mut num_cnt = vec![0; inp.m];
        let mut x_cnt = vec![0; inp.m];
        let mut y_cnt = vec![0; inp.m];
        for i in 0..inp.n {
            let (a, b) = inp.AB[i];
            let label = res_label[i];
            num_cnt[label] += 1;
            x_cnt[label] += a;
            y_cnt[label] += b;
        }
        let mut g_memo = Vec::new();
        for i in 0..inp.m {
            let gx = x_cnt[i] as f64 / num_cnt[i] as f64;
            let gy = y_cnt[i] as f64 / num_cnt[i] as f64;
            g_memo.push((gx, gy));
        }
        for i in 0..inp.n {
            let x = inp.AB[i].0 as f64;
            let y = inp.AB[i].1 as f64;
            let (xx, yy) = g_memo[res_label[i]];
            let mut pre_dist = calcdistf(x, y, xx, yy);

            for j in 0..inp.m {
                let (xx, yy) = g_memo[j];
                let temp_dist = calcdistf(x, y, xx, yy);
                if temp_dist < pre_dist {
                    pre_dist = temp_dist;
                    is_update = true;
                    res_label[i] = j;
                }
            }
        }
        if !is_update {
            for &(x, y) in g_memo.iter() {
                res_g.push(((x * ratio) as i32, (y * ratio) as i32))
            }
        }
    }
    (res_label, res_g)
}

fn print_gmemo(g_memo: Vec<(i32, i32)>, da: i32, db: i32) {
    for &(a, b) in g_memo.iter() {
        println!("{} {}", a + da, b + db);
    }
}
fn print_ans(ans: Vec<(usize, usize)>) {
    println!("{}", ans.len());
    for (a, b) in ans.iter() {
        println!("{} {}", a, b + 1);
    }
}
fn main() {
    get_time();
    input! {n: usize, m: usize, AB:[(i32,i32); n]};
    let (a, b) = AB[0];
    let mut ab = Vec::new();
    for i in 0..n {
        let (mut aa, mut bb) = AB[i];
        ab.push((aa - a, bb - b));
    }
    let inp = Input::new(n, m, ab);
    let n_class = 8;
    let (labels, g_memo) = kmeans(&inp, n_class, RATIO);

    let mut dist = vec![vec![0; inp.n + inp.m]; inp.n + inp.m];
    for i in 0..inp.n {
        let (x, y) = inp.AB[i];
        for j in i + 1..inp.n {
            let (xx, yy) = inp.AB[j];
            let d = 5 * 5 * calcdist(x, y, xx, yy);
            dist[i][j] = d;
            dist[j][i] = d;
        }
    }
    for i in 0..inp.m {
        let (x, y) = g_memo[i];
        for j in i + 1..inp.m {
            let (xx, yy) = g_memo[j];
            let d = calcdist(x, y, xx, yy);
            dist[i + n][j + n] = d;
            dist[j + n][i + n] = d;
        }
    }

    for i in 0..inp.n {
        let (x, y) = inp.AB[i];
        for j in 0..inp.m {
            let (xx, yy) = g_memo[j];
            let d = 5 * calcdist(x, y, xx, yy);
            dist[i][j + n] = d;
            dist[j + n][i] = d;
        }
    }

    let mut tempans: Vec<(usize, usize)> = Vec::new();
    tempans.push((1, 0));
    for i in 0..inp.m {
        tempans.push((2, i));
        for j in 0..inp.n {
            if labels[j] == i {
                tempans.push((1, j));
                tempans.push((2, i));
            }
        }
    }
    tempans.push((1, 0));

    let n_point = 210;

    assert_eq!(n_point, tempans.len());

    let mut tempscore = calcscore(&inp, &tempans, &dist);
    let mut cnt = 0;
    let mut kickcnt = 0;
    let mut bestcnt = 0;
    let mut bestans = tempans.clone();
    let mut bestscore = tempscore;
    let mut rng = Rng::new(20230424);
    while get_time() < TIMELIMIT {
        let (update, mut workingans) = opt2(&inp, &tempans, &dist);
        cnt += 1;

        if !update {
            let workingscore = calcscore(&inp, &workingans, &dist);
            if workingscore < bestscore {
                bestscore = workingscore;
                bestans = workingans.clone();
                bestcnt += 1;
            }
            // after opt2, change to neighbor
            workingans = doublebridge(&inp, &workingans, &mut rng);
            kickcnt += 1;
        }
        // renew variables
        // 100%採用
        tempans = workingans;
    }
    print_gmemo(g_memo, a, b);
    print_ans(bestans);
    eprintln!("cnt {}", cnt);
    eprintln!("kickcnt {}", kickcnt);
    eprintln!("bestcnt {}", bestcnt);
}

pub fn get_time() -> f64 {
    static mut STIME: f64 = -1.0; // 初期値
    let t = std::time::SystemTime::now() // nowを取得
        .duration_since(std::time::UNIX_EPOCH)
        .unwrap();
    // a.duration_since(b)だとa>bが前提
    let ms = t.as_secs() as f64 + t.subsec_nanos() as f64 * 1e-9;
    // as_secsが秒, .subsec_nanos()が小数点以下の秒
    unsafe {
        if STIME < 0.0 {
            STIME = ms; // 経過時間の初期化
        }
        // ローカル環境とジャッジ環境の実行速度差はget_timeで吸収しておくと便利
        #[cfg(feature = "local")]
        {
            (ms - STIME) * 1.3
        }
        #[cfg(not(feature = "local"))]
        {
            ms - STIME
        }
    }
}

fn opt2(
    inp: &Input,
    pre: &Vec<(usize, usize)>,
    dist: &Vec<Vec<i128>>,
) -> (bool, Vec<(usize, usize)>) {
    let mut res = pre.clone();
    let mut update: bool = false;
    for first in 1..(pre.len() - 2) {
        let (type1, mut idx1) = res[first];
        let (type2, mut idx2) = res[first + 1];
        if type1 == 2 {
            idx1 += inp.n;
        }
        if type2 == 2 {
            idx2 += inp.n;
        }
        for second in (first + 2)..pre.len() - 1 {
            let (type3, mut idx3) = res[second];
            let (type4, mut idx4) = res[second + 1];
            if type3 == 2 {
                idx3 += inp.n;
            }
            if type4 == 2 {
                idx4 += inp.n;
            }

            // println!("{} {} {} {}", first, nf, second, ns);
            let d1 = dist[idx1][idx2];
            let d2 = dist[idx3][idx4];
            let d3 = dist[idx1][idx3];
            let d4 = dist[idx2][idx4];
            if d1 + d2 > d3 + d4 {
                res[(first + 1)..(second + 1)].reverse();
                update = true;
                break;
            }
            if update {
                break;
            }
        }
    }
    (update, res)
}

// t1 a1,a2 t2 b1,b2, t3 c1,c2, t4 d1,d2, t5
// t1 a1,c2, t4  d1,b2, t3  c1,a2 t2 b1,d2 t5
fn doublebridge(inp: &Input, ans: &Vec<(usize, usize)>, rng: &mut Rng) -> Vec<(usize, usize)> {
    // let mut rng = Rng::new(20230424);
    let n = ans.len() - 1;
    let idx1 = rng.gen_range(1_usize, n - 8);
    let idx2 = rng.gen_range(idx1 + 2, n - 6);
    let idx3 = rng.gen_range(idx2 + 2, n - 4);
    let idx4 = rng.gen_range(idx3 + 2, n - 2);

    // let mut res = ans[0..=idx1].append(ans[idx1+1..=idx2])+ans[idx2+1..=idx3]+ans[idx3+1..=idx4]+[idx4+1..=n]
    let mut res: Vec<(usize, usize)> = Vec::new();

    for v in &ans[0..=idx1] {
        res.push(*v);
    }
    for v in &ans[idx3 + 1..=idx4] {
        res.push(*v);
    }
    for v in &ans[idx2 + 1..=idx3] {
        res.push(*v);
    }
    for v in &ans[idx1 + 1..=idx2] {
        res.push(*v);
    }
    for v in &ans[idx4 + 1..] {
        res.push(*v);
    }
    res
}