#include <bits/stdc++.h>
#include <cstdio>
#include <vector>
using namespace std;
using ll = long long;
const ll INF = 9e18;

ll dis(int x1, int y1, int x2, int y2) {
  return 1ll * (x2 - x1) * (x2 - x1) + 1ll * (y2 - y1) * (y2 - y1);
}

void Main() {
  int n, K;
  scanf("%d%d", &n, &K);
  vector<int> x(n), y(n);
  for (int i = 0; i < n; i++) {
    scanf("%d%d", &x[i], &y[i]);
  }
  vector<int> s;
  vector<int> vis(n);
  vis[0] = 1;
  s.push_back(0);
  for (int rnd = 2; rnd <= K; rnd++) {
    pair<ll, int> all = {0, -1};
    for (int i = 0; i < n; i++) {
      pair<ll, int> res = {INF, -1};
      if (!vis[i]) {
        for (auto j : s)
          res = min(res, {dis(x[i], y[i], x[j], y[j]), j});
        all = max(all, {res.first, i});
      }
    }
    vis[all.second] = 1;
    s.push_back(all.second);
  }
  for (auto v : s)
    cout << v << " ";
  cout << endl;
  for (int i = 0; i < n; i++) {
    pair<ll, int> res = {INF, -1};
    for (int j = 0; j < K; j++)
      res = min(res, {dis(x[i], y[i], x[s[j]], y[s[j]]), j});
    printf("%d ", res.second + 1);
  }
}

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    Main();
  }
}