#include using namespace std; const long long alpha = 5; typedef long long ll; struct solve { ll N, M; vector> planet_coordinate; vector> station_coordinate; vector> m; vector d; vector last; solve() { cin >> N >> M; planet_coordinate.resize(N); station_coordinate.resize(M); m.resize(N + M, vector(N + M)); d.resize(N + M, 1e18); last.resize(N + M, 1e18); for (int i = 0; i < N; i++) { cin >> planet_coordinate.at(i).first >> planet_coordinate.at(i).second; } station_coordinate.at(0) = make_pair(300, 300); station_coordinate.at(1) = make_pair(700, 300); station_coordinate.at(2) = make_pair(300, 700); station_coordinate.at(3) = make_pair(700, 700); station_coordinate.at(4) = make_pair(300, 500); station_coordinate.at(5) = make_pair(500, 300); station_coordinate.at(6) = make_pair(700, 500); station_coordinate.at(7) = make_pair(500, 700); } ll dist(pair a, pair b) { return ((a.first - b.first) * (a.first - b.first) + (a.second - b.second) * (a.second - b.second)); } ll distance(int i, int j) { return dist((i < N ? planet_coordinate.at(i) : station_coordinate.at(i - N)), (j < N ? planet_coordinate.at(j) : station_coordinate.at(j - N))) * (i < N ? 5 : 1) * (j < N ? 5 : 1); } ll get_shortest(int start, vector &used, queue &q) { for (int i = 0; i < N + M; i++) { for (int j = 0; j < N + M; j++) { m.at(i).at(j) = distance(i, j); } } priority_queue> pq; d.resize(N + M, 1e18); pq.push(make_pair(0, start)); ll Md = 1e18; int ind = 0; for (int i = 0; i < N + M; i++) { // cerr << "hoge" << d.at(i) << endl; d.at(i) = 1e18; } d.at(start) = 0; while (pq.size()) { int now = pq.top().second; pq.pop(); for (int i = 0; i < N + M; i++) { int next = i; // cerr << "-----" << now << ' ' << next << endl; // cerr << d.size() << endl; // cerr << m.at(0).size() << endl; // cerr << d.at(next) << endl; if (d.at(next) > d.at(now) + m.at(now).at(next)) { d.at(next) = d.at(now) + m.at(now).at(next); last.at(next) = now; // cout << "Md " << endl; if (N <= next) { pq.push(make_pair(d.at(next), next)); } else if (Md > d.at(next) && used.at(next) == false) { // cout << "/* code */" << endl; Md = d.at(next); ind = next; } } } } // cout << ind << endl; int next = ind; if (ind != -1) { stack s; while (ind != start) { s.push(ind); // cerr << "check " << ind << ' ' << last.at(ind) << endl; ind = last.at(ind); } while (s.size()) { q.push(s.top()); s.pop(); } } used.at(next) = true; return next; } void print_ans() { queue q; q.push(0); vector used(N + M, 0); used.at(0) = true; int start = 0; for (int i = 0; i < N; i++) { start = get_shortest(start, used, q); // cout << start << endl; } for (int i = 0; i < M; i++) { cout << station_coordinate.at(i).first << ' ' << station_coordinate.at(i).second << endl; } cout << q.size() << endl; while (q.size()) { int now = q.front(); // cout << now << endl; cout << 1 + now / N << ' ' << now % N + 1 << endl; q.pop(); } } }; int main() { solve s; s.print_ans(); return 0; }