#include <iostream>
#include <list>
#include <vector>
#include <string>
#include <stdio.h>
#include <stdint.h>
#include <iomanip>
using namespace std;

using uint = unsigned int;
using ll = long long;

#define CIN( LL , A ) LL A; cin >> A 
#define GETLINE( A ) string A; getline( cin , A ) 
#define GETLINE_SEPARATE( A , SEPARATOR ) string A; getline( cin , A , SEPARATOR ) 
#define FOR_LL( VAR , INITIAL , FINAL_PLUS_ONE ) for( ll VAR = INITIAL ; VAR < FINAL_PLUS_ONE ; VAR ++ ) 
#define FOR_ITR( ARRAY , ITR , END ) for( auto ITR = ARRAY .begin() , END = ARRAY .end() ; ITR != END ; ITR ++ ) 
#define REPEAT( HOW_MANY_TIMES ) FOR_LL( VARIABLE_FOR_REPEAT , 0 , HOW_MANY_TIMES ) 
#define RETURN( ANSWER ) cout << ( ANSWER ) << endl; return 0 
#define DOUBLE( PRECISION , ANSWER ) cout << fixed << setprecision( PRECISION ) << ( ANSWER ) << endl; return 0 
#define MIN( A , B ) A < B ? A : B;
#define MAX( A , B ) A < B ? B : A;
template <typename T> inline T Distance( const T& a , const T& b ){ return a < b ? b - a : a - b; }


#define SetAB( x , y )				\
						\
  a[num] = x;					\
  b[num] = y;					\
  ll p_num = ( x / W ) + ( y / H ) * Px;	\
  p[num] = p_num;				\
  ll& m_size_p_num = m_size[p_num];		\
  m[p_num][m_size_p_num] = num;			\
  m_size_p_num++;				\
						\



#define SetNear					\
						\
  FOR_LL( k , 0 , P ){				\
    ll (&m_k)[NM] = m[k];			\
    ll& m_size_k = m_size[k];			\
    ll (&near_k)[P][2] = near[k];		\
    ll (&E_min_k)[P] = E_min[k];		\
    FOR_LL( h , 0 , k ){			\
      ll (&m_h)[NM] = m[h];			\
      ll& m_size_h = m_size[h];			\
      ll (&near_kh)[2] = near_k[h];		\
      ll& E_min_kh = E_min_k[h];		\
      E_min_kh = 50000025;			\
      FOR_LL( i , 0 , m_size_k ){		\
	ll& m_ki = m_k[i];			\
	ll (&Ei)[NM] = E[m_ki];			\
	FOR_LL( j , 0 , m_size_h ){		\
	  ll& m_hj = m_h[j];			\
	  ll& Eij = Ei[m_hj];			\
	  if( Eij < E_min_kh ){			\
	    ll& E_min_hk = E_min[h][k];		\
	    E_min_kh = E_min_hk = Eij;		\
	    ll ( &near_hk )[2] = near[h][k];	\
	    near_kh[0] = near_hk[1] = m_ki;	\
	    near_kh[1] = near_hk[0] = m_hj;	\
	  }					\
	}					\
      }						\
    }						\
    ll (&near_kk)[2] = near_k[k];		\
    if( m_size_k == 1 ){			\
      near_kk[0] = near_kk[1] = m_k[0];		\
    } else if( m_size_k > 1 ){			\
      ll E_min_max_kk = -1;			\
      FOR_LL( i , 0 , m_size_k ){		\
	ll& m_ki = m_k[i];			\
	ll (&Ei)[NM] = E[m_ki];			\
	ll E_min_kk = 50000025;			\
	ll m_ki_min;				\
	ll m_kj_min;				\
	FOR_LL( j , 0 , m_size_k ){		\
	  if( j != i ){				\
	    ll& m_kj = m_k[j];			\
	    ll& Eij = Ei[m_kj];			\
	    if( Eij < E_min_kk ){		\
	      E_min_kk = Eij;			\
	      m_ki_min = m_ki;			\
	      m_kj_min = m_kj;			\
	    }					\
	  }					\
	}					\
	if( E_min_kk > E_min_max_kk ){		\
	  E_min_max_kk = E_min_kk;		\
	  near_kk[0] = m_ki_min;		\
	  near_kk[1] = m_kj_min;		\
	}					\
      }						\
    }						\
  }						\
						\


template <ll NM , ll P>
const ll& HeldKarp( const ll& k_start , const ll& k_goal , const ll& s , const ll (&k_valid)[P] , const ll& P_valid , const ll (&path_E)[NM][NM] , const ll (&near)[P][P][2] , const ll (&E_min)[P][P] , ll (&k_mid)[P] );

#define S 1 - 1
// #define S 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 * 2 - 1

int main()
{
  // constexpr const ll N = 2;
  // constexpr const ll M = 1;
  // constexpr const ll Px = 1;
  // constexpr const ll Py = 1;
  
  // constexpr const ll N = 3;
  // constexpr const ll M = 4;
  // constexpr const ll Px = 1;
  // constexpr const ll Py = 1;
  
  constexpr const ll N = 100;
  constexpr const ll M = 8;
  constexpr const ll Px = 4;
  constexpr const ll Py = 4;

  constexpr const ll W = ( 1000 / Px ) + 1;
  constexpr const ll H = ( 1000 / Py ) + 1;
  constexpr const ll P = Px * Py;
  constexpr const ll NM = N + M;
  constexpr const ll path_lim = 100;
  constexpr const ll f_lim = 10000000000;
  
  CIN( ll , N_dummy );
  CIN( ll , M_dummy );
  ll a[NM];
  ll b[NM];
  ll p[NM];
  ll m[P][NM];
  ll m_size[P] = {};
  FOR_LL( num , 0 , N ){
    CIN( ll , a_num );
    CIN( ll , b_num );
    SetAB( a_num , b_num );
  }
  ll E[NM][NM];
  FOR_LL( i , 0 , N ){
    ll (&Ei)[NM] = E[i];
    FOR_LL( j , 0 , i ){
      ll dx = a[i] - a[j];
      ll dy = b[i] - b[j];
      Ei[j] = E[j][i] = ( dx * dx + dy * dy ) * 25;
    }
  }
  ll E_min[P][P];
  ll near[P][P][2];
  SetNear;
  FOR_LL( num , N , NM ){
    ll E_min_max = 0;
    ll k_max;
    ll h_max;
    FOR_LL( k , 0 , P ){
      if( m_size[k] > 0 ){
	ll (&E_min_k)[P] = E_min[k];
	ll k_plus = k + 1;
	FOR_LL( h , 0 , k_plus ){
	  if( m_size[h] > 0 ){
	    ll& E_min_kh = E_min_k[h];
	    if( E_min_max < E_min_kh ){
	      E_min_max = E_min_kh;
	      k_max = k;
	      h_max = h;
	    }
	  }
	}
      }
    }
    ll E_min_max_min = 50000025;
    ll x_min;
    ll y_min;
    ll (&near_kh)[2] = near[k_max][h_max];
    ll& i_min = near_kh[0];
    ll& j_min = near_kh[1];
    FOR_LL( x , 0 , 1001 ){
      FOR_LL( y , 0 , 1001 ){
	ll dix = a[i_min] - x;
	ll diy = b[i_min] - y;
	ll djx = a[j_min] - x;
	ll djy = b[j_min] - y;
	ll E_min_max_yx = ( dix * dix + diy * diy ) * ( i_min < N ? 5 : 1 ) + ( djx * djx + djy * djy ) * ( j_min < N ? 5 : 1 );
	if( E_min_max_min > E_min_max_yx ){
	  E_min_max_min = E_min_max_yx;
	  x_min = x;
	  y_min = y;
	}
      }
    }
    cout << x_min << " " << y_min << endl;
    SetAB( x_min , y_min );
    ll num_plus = num + 1;
    FOR_LL( i , N , num_plus ){
      ll (&Ei)[NM] = E[i];
      FOR_LL( j , 0 , i ){
	ll dx = a[i] - a[j];
	ll dy = b[i] - b[j];
	Ei[j] = E[j][i] = ( dx * dx + dy * dy ) * ( j < N ? 5 : 1 );
      }
    }
    SetNear;
  }
  ll P_valid = 0;
  ll k_valid[P];
  FOR_LL( k , 0 , P ){
    if( m_size[k] > 0 ){
      k_valid[P_valid] = k;
    }
    P_valid++;
  }
  ll path[NM][NM][path_lim];
  ll path_length[NM][NM];
  ll path_E[NM][NM];
  bool computed_path_E[NM][NM] = {};
  FOR_LL( k , 0 , P_valid ){
    ll (&m_k)[NM] = m[k_valid[k]];
    ll& m_size_k = m_size[k_valid[k]];
    // 手抜き
    ll length_lim = max( m_size_k + 3 , (ll)10 );
    if( m_size_k == 1 ){
      ll& m_ki = m_k[0];
      path[m_ki][m_ki][0] = m_ki;
      path_length[m_ki][m_ki] = 1;
      path_E[m_ki][m_ki] = 0;
      computed_path_E[0][0] = true;
    } else if( m_size_k > 1 ){
      ll count = 0;
      FOR_LL( length , m_size_k , length_lim ){
	ll f_min = 1;
	FOR_LL( i , 0 , length ){
	  f_min *= m_size_k;
	}
	f_min--;
	if( f_min >= f_lim ){
	  length = length_lim;
	}
	FOR_LL( f , f_min , f_lim ){
	  ll f_copy = f;
	  ll path_current[path_lim];
	  bool used[NM] = {};
	  ll length_current = 0;
	  ll i_start = f_copy % m_size_k;
	  path_current[length_current] = i_start;
	  used[i_start] = true;
	  f_copy /= m_size_k;
	  length_current++;
	  while( length_current < length ){
	    ll i = f_copy % m_size_k;
	    if( i != path_current[length_current - 1] ){
	      path_current[length_current] = i;
	      used[i] = true;
	      f_copy /= m_size_k;
	      length_current++;
	    } else {
	      f_copy = 0;
	      length_current = length;
	    }
	  }
	  if( f_copy > m_size_k ){
	    f = f_lim;
	  } else if( f_copy != 0 ){
	    bool used_all = true;
	    FOR_LL( i , 0 , m_size_k ){
	      if( ! used[i] ){
		used_all = false;
		i = m_size_k;
	      }
	    }
	    if( used_all ){
	      ll path_E_current = 0;
	      FOR_LL( i , 1 , length ){
		ll& m_ki = m_k[path_current[i]];
		ll& m_kj = m_k[path_current[i - 1]];
		path_E_current += E[m_ki][m_kj];
	      }
	      ll& i_finish = path_current[length - 1];
	      bool& computed_path_E_ij = computed_path_E[i_start][i_finish];
	      ll& path_E_ij = path_E[i_start][i_finish];
	      if( computed_path_E_ij ? path_E_ij > path_E_current : true ){
		path_E_ij = path_E[i_finish][i_start] = path_E_current;
		ll (&path_ij)[path_lim] = path[i_start][i_finish];
		ll (&path_ji)[path_lim] = path[i_finish][i_start];
		FOR_LL( i , 0 , length ){
		  path_ij[i] = path_current[i];
		  path_ji[i] = path_current[length - 1 - i];
		}
		path_length[i_start][i_finish] = path_length[i_finish][i_start] = length;
		if( ! computed_path_E_ij ){
		  computed_path_E_ij = computed_path_E[i_finish][i_start] = true;
		}
	      }
	      count++;
	      if( count == 10000 ){
		length = length_lim;
	      }
	    }
	  }
	}
      }
    }
  }
  ll E_sum_min = 50000025 * P;
  ll k_start = p[0];
  ll k_min = k_start;
  ll k_mid_min[P];
  FOR_LL( k_next , 0 , P_valid ){
    ll& k = k_valid[k_next];
    if( k != k_start ){
      ll s = S;
      s ^= ( 1 << k_start );
      s ^= ( 1 << k );
      ll k_mid[P];
      ll E_sum = HeldKarp<NM,P>( k_start , k , 0 , k_valid , P_valid , path_E , near , E_min , k_mid );
      E_sum += HeldKarp<NM,P>( k , k_start , s , k_valid , P_valid , path_E , near , E_min , k_mid );
      E_sum += path_E[near[k_start][k][0]][near[k_mid[P_valid - 2]][k_start][1]] + path_E[near[k_start][k][1]][near[k][k_mid[1]][0]];
      if( E_sum_min > E_sum ){
	E_sum_min = E_sum;
	k_min = k;
	FOR_LL( k , 0 , P_valid ){
	  k_mid_min[k] = k_mid[k];
	}
      }
    }
  }
  ll P_valid_minus = P_valid - 1;
  ll& near_k_start_0 = P_valid == 1 ? P_valid_minus : near[k_mid_min[P_valid - 2]][k_start][1];
  ll& near_k_start_1 = P_valid == 1 ? P_valid_minus : near[k_start][k_min][0];
  ll (&path_k_start)[path_lim] = path[near_k_start_0][near_k_start_1];
  ll& path_length_k_start = path_length[near_k_start_0][near_k_start_1];
  ll num_start;
  FOR_LL( num , 0 , path_length_k_start ){
    if( path_k_start[num] == 0 ){
      num_start = num;
      num = path_length_k_start;
    }
  }
  ll V = path_length_k_start;
  FOR_LL( k , 0 , P_valid_minus ){
    ll& k_mid_min_k = k_mid_min[k];
    ll& near_k_0 = near[k_mid_min[( k + P_valid_minus ) % P_valid ]][k_mid_min_k][1];
    ll& near_k_1 = near[k_mid_min_k][k_mid_min[k+1]][0];
    V += path_length[near_k_0][near_k_1];
  }
  cout << V << endl;
  FOR_LL( num , num_start , path_length_k_start ){
    ll& i = path_k_start[num];
    if( i < N ){
      cout << 1 << " " << i << endl;
    } else {
      cout << 2 << " " << i - N << endl;
    }
  }
  FOR_LL( k , 0 , P_valid_minus ){
    ll& k_mid_min_k = k_mid_min[k];
    ll& near_k_0 = near[k_mid_min[( k + P_valid_minus ) % P_valid ]][k_mid_min_k][1];
    ll& near_k_1 = near[k_mid_min_k][k_mid_min[k+1]][0];
    ll (&path_k)[path_lim] = path[near_k_0][near_k_1];
    ll& path_length_k = path_length[near_k_0][near_k_1];
    FOR_LL( num , 0 , path_length_k ){
      ll& i = path_k[num];
      if( i < N ){
	cout << 1 << " " << i << endl;
      } else {
	cout << 2 << " " << i - N << endl;
      }
    }
  }
  FOR_LL( num , 0 , num_start ){
    ll& i = path_k_start[num];
    if( i < N ){
      cout << 1 << " " << i << endl;
    } else {
      cout << 2 << " " << i - N << endl;
    }
  }
  return 0;
}

template <ll NM , ll P>
const ll& HeldKarp( const ll& k_start , const ll& k_goal , const ll& s , const ll (&k_valid)[P] , const ll& P_valid , const ll (&path_E)[NM][NM] , const ll (&near)[P][P][2] , const ll (&E_min)[P][P] , ll (&k_mid)[P] )
{

  static ll answer_E[P][P][S];
  static ll answer_mid[P][P][P];
  static bool solved[P][P][S];
  ll (&answer_mid_kskg)[P] = answer_mid[k_start][k_goal]; 
  if( solved[k_start][k_goal][s] ){
    ll P_valid_minus = P_valid - 1;
    FOR_LL( k , 0 , P_valid_minus ){
      k_mid[k] = answer_mid_kskg[k];
    }
    return answer_E[k_start][k_goal][s];
  }
  if( s == 0 ){
    k_mid[0] = answer_mid_kskg[0] = k_start;
    k_mid[1] = answer_mid_kskg[1] = k_goal;
    solved[k_start][k_goal][s] = true;
    return answer_E[k_start][k_goal][s] = answer_E[k_goal][k_start][s] = E_min[k_start][k_goal];
  }
  ll s_copy = s;
  ll card = 0;
  ll k_s[P];
  ll k_s_i = 0;
  while( s_copy != 0 ){
    if( s_copy % 2 == 1 ){
      k_s[card] = k_s_i;
      card++;
    }
    k_s_i++;
  }
  ll E_current_min = 7500003751;
  ll k_mid_current_min[P];
  ll k_mid_current[P];
  ll card_plus = card + 1;
  FOR_LL( i , 0 , card ){
    ll& k = k_s[i];
    ll E_current = HeldKarp<NM,P>( k_start , k , 0 , k_valid , P_valid , path_E , near , E_min , k_mid );
    E_current += HeldKarp<NM,P>( k_start , k , s ^ ( 1 << k ) , k_valid , P_valid , path_E , near , E_min , k_mid_current );
    E_current += path_E[near[k_start][k][1]][near[k][k_mid_current[1]][0]];
    if( E_current_min < E_current ){
      E_current_min = E_current;
      FOR_LL( j , 0 , card_plus ){
	k_mid_current_min[j] = k_mid_current[j];
      }
    }
  }
  answer_mid_kskg[0] = k_start;
  FOR_LL( i , 0 , card_plus ){
    answer_mid_kskg[i+1] = k_mid[i+1] = k_mid_current_min[i];
  }
  solved[k_start][k_goal][s] = true;
  return answer_E[k_start][k_goal][s] = answer_E[k_goal][k_start][s] = E_current_min;

}