#include <CGAL/Exact_predicates_inexact_constructions_kernel.h>
#include <CGAL/Delaunay_triangulation_2.h>
#include <CGAL/Triangulation_vertex_base_with_info_2.h>
#include <CGAL/Point_set_2.h>

#include <vector>
#include <iostream>
#include <algorithm>
#include <iterator>
#include <unordered_set>
#include <queue>
#include <list>
using namespace std;

#define PRINT2D(vecvec) for(int i = 0; i < vecvec.size(); i++){cout<<i<<" neighbourhood: "; for(auto x : vecvec[i]){cout<<x<<" ";} cout<<endl;}
#define PRINT1D(vec) for(int x : vec){cout<<x<<" ";} cout<<endl;

typedef CGAL::Exact_predicates_inexact_constructions_kernel K;
typedef CGAL::Triangulation_vertex_base_with_info_2<int, K> Vb;
typedef CGAL::Triangulation_data_structure_2<Vb> Tds;
typedef CGAL::Delaunay_triangulation_2<K, Tds> Delaunay0;
typedef CGAL::Point_set_2<K, Tds> Delaunay;

typedef Delaunay::Point Point;
typedef Delaunay::Edge_iterator Edge_iterator;
typedef Delaunay::Vertex_handle Vertex_handle;

typedef vector<pair<double, double> > Points_list;
typedef vector<vector<int> > Neighbour_list;
typedef pair<int, int> Edge;

const int K_NEAREST = 10;

Neighbour_list build_Delaunay_graph(Delaunay& T, int points_amount) {
   Neighbour_list neighbour_list(points_amount);
   vector<unordered_set<int> > unique_edges(points_amount);
   Delaunay::Finite_vertices_iterator vit;

   // Triangulation edges
   Delaunay::Vertex_circulator vc, done;
   for (vit = T.finite_vertices_begin(); vit != T.finite_vertices_end(); ++vit)
   {
      int act_point = vit->info();
      vc = vit->incident_vertices();
      done = vc;
      if (vc != 0)
      {
         do {
            if (T.is_infinite(vc)) continue;
            unique_edges[act_point].insert(vc->info());
            unique_edges[vc->info()].insert(act_point);
         } while(++vc != done);
     }
   }

   // 10 nearest Edges
   for (vit = T.finite_vertices_begin(); vit != T.finite_vertices_end(); ++vit)
   {
      vector <Vertex_handle> L;
      int act_point = vit->info();
      T.nearest_neighbors( vit, K_NEAREST+1, back_inserter(L) );
      for (int i=0; i< L.size(); i++)
      {
         if(L[i]->info() != act_point){
            unique_edges[act_point].insert(L[i]->info());
            unique_edges[L[i]->info()].insert(act_point);
         }
      }

   }

   for(int i = 0; i < points_amount; i++) {
      for(const int &el : unique_edges[i]) {
         neighbour_list[i].push_back(el);
      }
   }

   return neighbour_list;
}

inline double euclid_sq_distance(int v, int w, Points_list& points) {
   double x = points[v].first - points[w].first;
   double y = points[v].second - points[w].second;
   return x*x+y*y;
}

class Prim {
   Neighbour_list neighbour_list;
   int vertex_amount;
   vector<bool> used;
   priority_queue<pair<double, Edge> > tree_dist;
   Points_list points_list;

   public:
   Prim(Neighbour_list neighbour_list, Points_list points_list, int vertex_amount) {
      this->neighbour_list = neighbour_list;
      this->vertex_amount = vertex_amount;
      this->points_list = points_list;
      vector<bool> t(vertex_amount);
      for(int i = 0; i < vertex_amount; i++) {
         t[i] = false;
      }
      this->used = t;
   }

   vector<Edge> spanning_tree() {
      used[0] = true;
      relax(0);
      vector<Edge> tree;

      while (tree.size() != vertex_amount-1){
         Edge closest = get_closest_edge();
         tree.push_back(closest);
         relax(closest.second);
         used[closest.second] = true;
      }
      return tree;
   }

   private:
   Edge get_closest_edge() {
      int res = -1;
      while(tree_dist.size()){
         Edge top = tree_dist.top().second;
         tree_dist.pop();
         if(!used[top.second]) {
            return top;
         }
      }
      return make_pair(0, 0);
   }

   void relax(int vertex) {
      for(int neigh : neighbour_list[vertex]) {
         if(!used[neigh]){
            tree_dist.push(make_pair(-euclid_sq_distance(vertex, neigh, points_list), make_pair(vertex, neigh)));
         }
      }
   }
};

Neighbour_list build_doubled_leafs_tree(vector<Edge>& tree, int vertex_amount) {
   Neighbour_list neighbour_list(vertex_amount);
   for(auto edge : tree) {
      neighbour_list[edge.first].push_back(edge.second);
      neighbour_list[edge.second].push_back(edge.first);
   }
   for(int i = 0; i < vertex_amount; i++){
      if(neighbour_list[i].size() == 1){
         neighbour_list[i].push_back(neighbour_list[i][0]);
         neighbour_list[neighbour_list[i][0]].push_back(i);
      }
   }
   return neighbour_list;
}

vector<int> convex_hull_to_tsp(vector<int>& odd, Points_list& points_list, vector<int>& convex_hull){
   priority_queue<pair<double, int> > q;
   unordered_set<int> not_on_hull;
   for(int i = 0; i < odd.size(); i++){
      bool on_hull = false;
      for(int j = 0; j < convex_hull.size(); j++){
         if(odd[i] == convex_hull[j]){
            on_hull = true;
            break;
         }
      }
      if(!on_hull){
         not_on_hull.insert(odd[i]);
      }
   }
   list<int> tsp;
   for(int x : convex_hull){
      tsp.push_back(x);
   }

   // initialize queue
   for(int vert : not_on_hull){
      double min_dist = 0;
      for(int j = 0; j < convex_hull.size(); j++){
         min_dist = min(min_dist, euclid_sq_distance(vert, convex_hull[j], points_list));
      }
      q.push(make_pair(min_dist, vert));
   }

   while(not_on_hull.size() != 0){
      auto top = q.top();
      q.pop();
      if(not_on_hull.find(top.second) == not_on_hull.end()){
         continue;
      }
      not_on_hull.erase(top.second);
      auto minimizing_vert = tsp.begin();
      auto it = tsp.begin();
      while(next(it) != tsp.end()){
         auto prev = it;
         it++;
         double long dist = sqrt(euclid_sq_distance(*it, top.second, points_list)) + sqrt(euclid_sq_distance(*prev, top.second, points_list));
         if(dist < sqrt(euclid_sq_distance(*minimizing_vert, top.second, points_list)) + sqrt(euclid_sq_distance(*(next(minimizing_vert)), top.second, points_list))){
            minimizing_vert = prev;
         }
      }
      auto prev = it;
      it = tsp.begin();
      double long dist = sqrt(euclid_sq_distance(*it, top.second, points_list)) + sqrt(euclid_sq_distance(*prev, top.second, points_list));
      if(dist < sqrt(euclid_sq_distance(*minimizing_vert, top.second, points_list)) + sqrt(euclid_sq_distance(*(next(minimizing_vert)), top.second, points_list))){
         minimizing_vert = prev;
      }
      tsp.insert(minimizing_vert, top.second);
   }

   vector<int> result;
   for(int x : tsp){
      result.push_back(x);
   }
   return result;
}

vector<int> get_odd_vertices(Neighbour_list& neighbour_list, int vertex_amount){
   vector<int> result;
   for(int i = 0; i < vertex_amount; i++){
      if(neighbour_list[i].size() % 2){
         result.push_back(i);
      }
   }
   return result;
}

vector<Edge> matching_from_tsp(vector<int> tsp, Points_list& points_list){
   if(tsp.size() == 2){
      return {make_pair(tsp[0], tsp[1])};
   }
   vector<Edge> odd;
   vector<Edge> even;
   for(int i = 0; i < tsp.size() - 3; i += 2){
      odd.push_back(make_pair(tsp[i], tsp[i+1]));
      even.push_back(make_pair(tsp[i+1], tsp[i+2]));
   }
   odd.push_back(make_pair(tsp[tsp.size()-2], tsp[tsp.size()-1]));
   even.push_back(make_pair(tsp[tsp.size()-1], tsp[0]));
   double odd_cost, even_cost;
   odd_cost = even_cost = 0;

   for(Edge e : odd){
      odd_cost += sqrt(euclid_sq_distance(e.first, e.second, points_list));
   }
   for(Edge e : even){
      even_cost += sqrt(euclid_sq_distance(e.first, e.second, points_list));
   }
   if(odd_cost < even_cost){
      return odd;
   } else {
      return even;
   }
}

Edge ord_edge(int x, int y){return make_pair(min(x, y), max(x, y));}

void find_euler_cycle(map<Edge, int>& edges_cnt, Neighbour_list& neighbour_list, vector<int>& result, int vert){
   for(int i = neighbour_list[vert].size() - 1; i >= 0; i--){
      int next = neighbour_list[vert][i];
      if(edges_cnt[ord_edge(vert, neighbour_list[vert][i])] != 0){
         edges_cnt[ord_edge(vert, next)]--;
         neighbour_list[vert].pop_back();
         find_euler_cycle(edges_cnt, neighbour_list, result, next);
      } else {
         neighbour_list[vert].pop_back();
      }
   }
   result.push_back(vert);
}

vector<int> euler_cycle(Neighbour_list neighbour_list, int vertex_amount){
   map<Edge, int> edges_cnt;
   for(int i = 0; i < vertex_amount; i++){
      for(int j = 0; j < neighbour_list[i].size(); j++){
         if(edges_cnt.find(ord_edge(i, neighbour_list[i][j])) != edges_cnt.end()){
            edges_cnt[ord_edge(i, neighbour_list[i][j])]++;
         } else {
            edges_cnt[ord_edge(i, neighbour_list[i][j])] = 1;
         }
      }
   }
   for(auto entry : edges_cnt){edges_cnt[entry.first] = entry.second /= 2;}
   vector<int> result;
   find_euler_cycle(edges_cnt, neighbour_list, result, 0);
   cout<<"przed return"<<endl;
   return result;
}

vector<int> euler_cycle_to_tsp(vector<int> euler_cycle, int vertex_amount){
   vector<int> result;
   vector<bool> used(vertex_amount);
   for(int x : euler_cycle){
      if(!used[x]){
         used[x] = true;
         result.push_back(x);
      }
   }
   return result;
}

vector<int> get_aprox_tsp(Points_list& points_list, vector<pair<Point, int> >& points, int vertex_amount){
   Delaunay T;
   T.insert(points.begin(), points.end());
   Neighbour_list neighbour_list = build_Delaunay_graph(T, vertex_amount);
   Prim prim = Prim(neighbour_list, points_list, vertex_amount);
   vector<Edge> tree = prim.spanning_tree();
   neighbour_list = build_doubled_leafs_tree(tree, vertex_amount);

   Delaunay K;
   points.clear();
   vector<int> odd = get_odd_vertices(neighbour_list, vertex_amount);
   for (int i=0; i<odd.size(); i++)
   {
      points.push_back( make_pair(Point(points_list[odd[i]].first,points_list[odd[i]].second), odd[i]) );
   }
   K.insert(points.begin(), points.end());

   vector<int> convex_hull;
   Delaunay::Vertex_circulator vc, done;
   vc = K.incident_vertices(K.infinite_vertex()),
   done = vc;
   if (vc != 0)
   {
     do { convex_hull.push_back(vc->info());
        } while(++vc != done);
   }

   vector<int> partial_tsp = convex_hull_to_tsp(odd, points_list, convex_hull);
   vector<Edge> matching = matching_from_tsp(partial_tsp, points_list);
   for(Edge e : matching){
      neighbour_list[e.first].push_back(e.second);
      neighbour_list[e.second].push_back(e.first);
   }

   PRINT2D(neighbour_list);

   vector<int> euler = euler_cycle(neighbour_list, vertex_amount);
   cout<<"po return"<<endl;
   vector<int> res = euler_cycle_to_tsp(euler, vertex_amount);
   return res;
}

double tsp_cost(vector<int> tsp_cycle, Points_list& points_list, int vertex_amount){
   double result = 0;
   for(int i = 0; i < vertex_amount - 1; i++){
      result += sqrt(euclid_sq_distance(tsp_cycle[i], tsp_cycle[i+1], points_list));
   }
   result += sqrt(euclid_sq_distance(tsp_cycle[vertex_amount - 1], tsp_cycle[0], points_list));
   return result;
}

void read_input(vector<pair<Point, int> >& points, Points_list& points_list, int& n) {
   double x,y;
   cin >> n;
   for (int i=0; i<n; i++)
   {
      cin >> x >> y;
      points.push_back( make_pair(Point(x,y), i) );
      points_list.push_back( make_pair(x, y) );
   }
}

int main( )
{
   int zes;
   cin>>zes;
   while(zes--){
      vector<pair<Point, int> > points;
      Points_list points_list;
      int vertex_amount;

      read_input(points, points_list, vertex_amount);

      vector<int> tsp_cycle = get_aprox_tsp(points_list, points, vertex_amount);
      cout<<tsp_cycle.size()<<endl;
      PRINT1D(tsp_cycle);
      for(int x : tsp_cycle){
         cout<<x<<" ";
      }
      cout<<endl<<tsp_cost(tsp_cycle, points_list, vertex_amount)<<endl;

      return 0;
   }
}