#include "pch.h"
#include <iostream>
#include <cmath>
#include <string>
#include <iomanip>
#include <regex>
#include <cstdlib>

using namespace std;

struct City {
	double x, y;
};

int main() {
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
	int n, vertex_1, vertex_2; cin >> n;
	int amount = 4; // кол-во особей первоначально
	double **w = new double*[n];
	int **path = new int*[amount];
	for (int i = 0; i < amount; i++) {
		path[i] = new int[n + 1];
		for (int j = 0; j < n; j++)
			path[i][j] = -1;
	}
	int *visited = new int[n];
	City *cities = new City[n];

	// коорд в матрицу весов
	for (int i = 0; i < n; i++)
		cin >> cities[i].x >> cities[i].y;
	for (int i = 0; i < n; i++) {
		w[i] = new double[n];
		visited[i] = 0;
		for (int j = 0; j < n; j++) {
			double x1 = cities[i].x, y1 = cities[i].y;
			double x2 = cities[j].x, y2 = cities[j].y;
			w[i][j] = sqrt((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1));
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			cout << i << " - > " << j << " : " << w[i][j] << endl;
		}
	}
	// создание первоначальной популяции
	for (int i = 0; i < amount; i++) {
		int start_pos = rand() % n;
		path[i][0] = start_pos;
		for (int j = 1; j < n; j++) {
			int next_pos;
			while (true) {
				bool cond = true;
				next_pos = rand() % n;
				for (int k = 0; k < n; k++) {
					if (k != j) {
						if (next_pos == path[i][k] || next_pos == path[i][0]) {
							cond = false;
							break;
						}
					}
				}
				if (cond == true)
					break;
			}
			path[i][j] = next_pos;
		}
		path[i][n] = start_pos;
	}

	// считаем длину каждой особи
	double best_individual = 1000000000, worst_individual = -1;
	int number_best_individual, number_worst_individual;
	for (int i = 0; i < amount; i++) {
		double SUM = 0;
		cout << path[i][0] << " ";
		for (int j = 1; j <= n; j++) {
			cout << path[i][j] << " ";
			SUM += w[path[i][j - 1]][path[i][j]];
		}
		cout << ": " << SUM << endl;
		if (SUM < best_individual) {
			best_individual = SUM;
			number_best_individual = i;
		}
		else if (SUM > worst_individual) {
			worst_individual = SUM;
			number_worst_individual = i;
		}
	}
	cout << best_individual << " " << number_best_individual << endl << worst_individual << " " << number_worst_individual << endl;


	for (int start_mut = 0; start_mut < 3; start_mut++) {
		// мутация
		int counter = n - 1;
		path[number_worst_individual][0] = path[number_best_individual][0];
		path[number_worst_individual][n] = path[number_best_individual][n];
		for (int h = 1; h < n; h++) {
			path[number_worst_individual][h] = path[number_best_individual][counter];
			counter--;
		}

		best_individual = 100000000; worst_individual = -1;

		for (int i = 0; i < amount; i++) {

			double SUM = 0;
			cout << path[i][0] << " ";
			for (int j = 1; j <= n; j++) {
				cout << path[i][j] << " ";
				SUM += w[path[i][j - 1]][path[i][j]];
			}
			cout << ": " << SUM << endl;
			if (SUM < best_individual) {
				best_individual = SUM;
				number_best_individual = i;
			}
			else if (SUM > worst_individual) {
				worst_individual = SUM;
				number_worst_individual = i;
			}
		}
		cout << best_individual << " " << number_best_individual << endl << worst_individual << " " << number_worst_individual << endl;
	}

	return 0;
}