#include <iostream>
#include <fstream> // подключаем библиотеку
#include <algorithm>
#include <vector>
#include <cstdlib>
#include <ctime> // содержит time()
#include <cmath>
#include <numeric>
#include <random>

using namespace std;


float Euklidus(int i, int j, vector<pair<int, int> >& V) {
    float temp = sqrt(pow(V[i].first - V[j].first, 2) + pow(V[i].second - V[j].second, 2));
    return temp;
}

void f(int i, int j, float& answer, vector<vector<float> >& M, vector<int>& way) {
    int n = way.size();
    float answer_minus = 0;
    float answer_plus = 0;
    if (abs(i - j) > 1) {
        answer_minus = M[way[i-1]][way[i]] + M[way[i]][way[i+1]] + M[way[j]][way[j-1]] + M[way[j]][way[j+1]];
        answer_plus = M[way[i-1]][way[j]] + M[way[j]][way[i+1]] + M[way[j-1]][way[i]] + M[way[i]][way[j+1]];
    } else if (abs(i - j) == 1) {
        answer_minus = M[way[i-1]][way[i]] + M[way[j]][way[j+1]];
        answer_plus = M[way[i-1]][way[j]] + M[way[i]][way[j+1]];
    }
    if (answer_plus < answer_minus) {
        swap(way[i], way[j]);
        answer += (answer_plus - answer_minus);
    } else {
        ;
    }
}

void g(int i, int j, float& answer, vector<vector<float> >& M, vector<int>& way) { // i < j != 0
    int n = way.size();
    float answer_minus = 0;
    float answer_plus = 0;
    if (abs(i - j) > 0) {
        answer_minus = M[way[i+1]][way[i]] + M[way[j]][way[j-1]];
        answer_plus = M[way[i]][way[j-1]] + M[way[i+1]][way[j]];
        if (true) {
            for (int t = 1; t < ((j-i-1) / 2) + 1; ++t) {
                swap(way[i+t], way[j-t]);
            }
            answer += (answer_plus - answer_minus);
        }
    }
    /* else if (abs(i - j) == 1) {
        answer_minus = M[way[i]][way[i+1]] + M[way[(j+1) % n]][way[j]] + M[way[i+1]][way[j]];
        answer_plus = M[way[i]][way[j]] + M[way[i]][way[j+1]];
    }
    if (answer_plus < answer_minus) {
        for (int t = 1; t < ((j-i-1) / 2) + 1; ++t) {
            swap(way[i+t], way[j-t]);
        }
        answer += (answer_plus - answer_minus);
    } else {
        ;
    }*/
}

int main() {
    /*ifstream file; // создаем объект класса ifstream
    file.open("..\\input.txt"); // открываем файл
    int n;
    file >> n;*/
    int n;
    cin >> n;
    if (n == 0) {
        return 0;
    } else if (n == 1) {
        cout << 0 << endl;
        return 0;
    } else if (n == 2) {
        cout << 0 << ' ' << 1 << ' ' << 0 << endl;
        return 0;
    }
    int R = 500000;
    int randomDigits[R] = {};
    srand(time(NULL));
    for (int i = 0; i < R; i++) {
        randomDigits[i] = rand() % n; // n-1 ????
        if ((randomDigits[i]) == 0) {
            randomDigits[i]++;
        }
    }
    pair<int, int> p;
    vector<pair<int, int> > V(n);
    vector<vector<float> > M(n, vector<float>(n, 0));
    for (int i = 0; i < n; ++i) {
        cin >> p.first >> p.second;
        //file >> p.first >> p.second;
        V[i] = p;
    }
    float t;
    for (int i = 0; i < n-1; ++i) {
        for (int j = i+1; j < n; ++j) {
            t = Euklidus(i, j, V);
            M[i][j] = t;
            M[j][i] = t;
        }
    }
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            cout << M[i][j] << ' ';
        }
        cout << endl;
    }
    vector<bool> color(n);
    int colored = 1;
    color[0] = true;
    int current_vertex = 0;
    vector<int> way(n);
    //vector<float> dist_to_previous(n);
    way[0] = 0;
    float all_dist = 0;
    for (int k = 1; k < n; ++k) {
        int vertex_min_dist;
        float min_dist = 1000000;
        for (int i = 0; i < n; ++i) {
            if (!color[i]) {
                if (M[current_vertex][i] < min_dist && i != current_vertex) {
                    min_dist = M[current_vertex][i];
                    vertex_min_dist = i;
                }
            }
        }
        cout << endl;
        cout << "cur vertex:= " << vertex_min_dist <<  "   min_dist = " << min_dist << endl;
        color[vertex_min_dist] = true;
        way[k] = vertex_min_dist;
        current_vertex = vertex_min_dist;
        for (int l = 0; l < n; ++l) {
            cout << color[l] << ' ';
        }
        cout << endl;
    }
    way.push_back(0);

    float answer = 0;
    for (int i = 0; i < n-1; ++i) {
        answer += M[way[i]][way[i+1]];
    }
    answer += M[way[n-1]][way[0]];
    cout << "answer before = " << answer << endl;
    for (int i = 0; i < n; ++i) {
        cout << way[i]+1 << ' ';
    }
    int counter = 0;
    int left;
    int right;
    for (int i = 1; i < R-1; ++i) {
        left = min(randomDigits[i], randomDigits[(i+1) % n]);
        right = max(randomDigits[i], randomDigits[(i+1) % n]);
        f(left, right, answer, M, way);
        ++counter;
    }
    cout << way[0]+1 << endl;

    cout << "answer after = " << answer << endl;
    for (int i = 0; i < n; ++i) {
        cout << way[i]+1 << ' ';
    }
    cout << way[0]+1 << ' ' << counter << endl;


    g(1, 4, answer, M, way);

    cout << "answer after g = " << answer << endl;
    for (int i = 0; i < n; ++i) {
        cout << way[i]+1 << ' ';
    }
    cout << way[0]+1 << ' ' << counter << endl;

    vector<int> permut(n);
    generate(permut.begin(), permut.end(), [t = 0] () mutable { return t++; });
    random_device rd;
    mt19937 g(rd());
    shuffle(permut.begin()+1, permut.end(), g);
    permut.push_back(permut[0]);
    for (auto elem : permut) {
        cout << elem << ' ';
    }
    cout << endl;
}