import java.util.*;

/**
 * Spider Pig's Doughnut-Eating Spree
 *
 * This program generates an optimal east-to-west doughnut-eating tour
 * for Spider Pig.
 *
 * For the UMD High School Programming Contest, 2008.
 * @author Dave Mount
 */
public class SpiderPig {
	
	static int n;					// number of doughnuts
	static int[] dx;				// doughnut x-coordinates
	static int[] dy;				// doughnut y-coordinates
	static int[] position;			// doughnut's position on final path 
									// (0=outbound, 1=inbound)

	/** Compute distance between two points.
	 *  
	 *  Returns the distance between points i and j using the Manhattan
	 *  (or checkerboard) distance.
	 */
	private static int distance(int i, int j) {
		return Math.abs(dx[i] - dx[j]) + Math.abs(dy[i] - dy[j]);
	}
	
	/** Main program.
	 *  
	 *  Reads inputs, invokes path generator, and outputs path and 
	 *  length. To break the symmetry between the inbound portion and 
	 *  outbound portions of the path, we assume that there are at 
	 *  least 2 doughnuts, and assume that the outbound portion starts 
	 *  with by going from doughnut 0 to doughnut 1.
	 */
	public static void main(String[] args) throws Exception {
		
										// read input
		Scanner scanner = new Scanner( System.in );
		n = scanner.nextInt();			// input number of doughnuts
		if (n < 2) {
			System.out.println("Error: Need at least 2 doughnuts");
			System.exit(0);
		}
		
		dx = new int[n];				// allocate doughnut coords
		dy = new int[n];
		position = new int[n];			// allocate position info
		
		for (int i = 0; i < n; i++) {	// input coords and yumminess
			dx[i] = scanner.nextInt();
			dy[i] = scanner.nextInt();
			if (i > 0 && dx[i] <= dx[i-1]) {
				System.out.println("Error: x-coords must increase");
				System.exit(0);
			}
		}
										// echo input
		System.out.print("Doughnuts:");		
		for (int i = 0; i < n; i++) {	// output doughnut locations
			System.out.print(" (" + dx[i] + "," + dy[i] + ")");
		}
		System.out.println();
		
		generatePath();					// generate the path
		printPath(position);			// print path
		System.out.println("Length: " + getLength(position));

		//--------------------------------------------------------------
		// THE FOLLOWING IS FOR DEBUGGING ONLY!!! REMOVE FROM FINAL DISTRIBUTION
		//--------------------------------------------------------------
		// int length1 = getLength(position);
		// System.out.println("\nGenerating path by brute force (for debugging):");
		// generatePathByBruteForce();		// brute force (for debugging)
		// System.out.println();
		// printPath(position);				// print path and length
		// int length2 = getLength(position);
		// System.out.println("  Length2 = " + getLength(position));
		// if (length1 != length2)
		// 	System.out.println("Bug: Length mismatch!!!");
		//--------------------------------------------------------------
	}
	
	/** Generates the length of the path given position info.
	 *  
	 */
	private static int getLength(int[] p) {
		int length = 0; 				// total path length
		int previous = 0; 				// previous item on p
		int d1Side = p[1]; 				// the side with doughnut[1]
		for (int i = 1; i < n; i++) {	// output the outbound p
			if (p[i] == d1Side || i == n - 1) {
				length += distance(previous, i);
				previous = i;
			}
		}
		for (int i = n - 2; i >= 0; i--) { // output the return p
			if (p[i] != d1Side || i == 0) {
				length += distance(previous, i);
				previous = i;
			}
		}
		return length;
	}

	/** Prints a path given position info.
	 * 
	 *	To avoid ambiguity, the path is printed so that p[1] appears
	 *	on the outbound segment.
	 */
	private static void printPath(int[] p) {
		int d1Side = p[1]; 			// the side with doughnut[1]
		System.out.print("Path: 0");
		for (int i = 1; i < n; i++) { 		// output the outbound p
			if (p[i] == d1Side || i == n - 1) {
				System.out.print(" " + i);
			}
		}
		for (int i = n - 2; i >= 0; i--) { // output the return p
			if (p[i] != d1Side || i == 0) {
				System.out.print(" " + i);
			}
		}
		System.out.println();
	}


	/** Generates the optimal Doughnut path.
	 *  
	 *  Generates the doughnut path given n doughnuts with coordinates
	 *  (dx[i],dy[i]). The result is stored in the boolean array position,
	 *  where position[i] = 0 if doughnut i is on the outbound segment of
	 *  the path and 1 otherwise. We assume that the x coordinates are 
	 *  increasing.
	 */
	private static void generatePath() {
		/* ------------------- INSERT CODE HERE ---------------------*/
		
		/* ===================SOLUTION STARTS HERE===================*/
		
		/* -------------------------------------------------------------
		 *  We solve the problem through the application of dynamic
		 *  programming. We construct an array C[n][n], such that
		 *  C[i][j] holds the total length of the shortest pair of paths
		 *  that traverse the doughnuts 0..max(i,j), where the outbound 
		 *  path ends at doughnut i and the inbound path ends at 
		 *  doughnut j. (Note that this function is symmetric in that 
		 *  C[i][j] == C[j][i]. In theory we only need to compute half
		 *  the array, but we will compute both parts for simplicity.)
		 *  Observe that C[n-1][n-1] is the final optimal path length.
		 *  
		 *  To help us recover the path, we observe that each value
		 *  C[i][j] arose by adding a single segment onto some prior
		 *  entry. If i > j, the prior entry is of the form C[k][j]
		 *  and if i < j, the prior entry is of the form C[i][k]. We
		 *  create a parallel array P, such that P[i][j] holds this
		 *  value k.
		 *  
		 *  For the basis case, we set C[0][0] = 0. To compute C[i][j]
		 *  in general, let us assume that j <= i, since the other case
		 *  is symmetric (switching i and j and setting S[i][j] = 1
		 *  rather than 0). We consider the following cases:
		 *  
		 *  j == i: We know that the edge (i-1,i) must be on one path
		 *  	or the other. By symmetry we know that C[i-1][i] =
		 *  	C[i][i-1], so it doesn't matter which side the previous
		 *  	segment is on. We put it on the outbound side. Thus we 
		 *  	have:
		 *  
		 *  	C[i][i] = C[i-1][i] + dist(i-1,i).
		 *  	P[i][i] = i-1
		 *  
		 *  j == i-1: Item i is preceded by either i-2, i-3, ..., 0.
		 *  	Since we don't know which, we try them all and take
		 *  	the smallest. Thus we have:
		 *  
		 *  	C[i][j] = min_{0<=k<=i-2} C[k,j] + dist(k,i).
		 *  	P[i][j] = the value k giving the minimum
		 *  
		 *  j < i-1: Item i must be connected to i-1 (since otherwise
		 *  	it would be skipped). Thus we have:
		 *  
		 *  	C[i][j] = C[i-1][j] + dist(i-1,i)
		 *  	P[i][j] = i-1
		 *  
		 *  For the basis case we set P[0][0] = -1.
		 * -------------------------------------------------------------
		 */

		int[][] C = new int[n][n];		// path length
		int[][] P = new int[n][n];		// path predecessor
		
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (j == i) {
					if (i == 0) {		// basis case (i==j==0)
						C[0][0] = 0;
						P[0][0] = -1;
					}
					else /* ((i == j) > 0) */ {
						C[i][i] = C[i-1][i] + distance(i-1, i);
						P[i][i] = i-1;
					}
				}
				else if (j < i) {		// last one is on outbound side
					if (j == i-1) {
						int minCost = C[0][j] + distance(0, i);
						int minIndex = 0;
						for (int k = 1; k < i; k++) {
							int thisCost = C[k][j] + distance(k, i);
							if (thisCost < minCost) {
								minCost = thisCost;
								minIndex = k;
							}
						}
						C[i][j] = minCost;
						P[i][j] = minIndex;
					}
					else /* (j < i-1) */ {
						C[i][j] = C[i-1][j] + distance(i-1,i);
						P[i][j] = i-1;
					}
				}
				else /* (i < j) */ {	// last one is on inbound side
					if (i == j-1) {
						int minCost = C[i][0] + distance(0, j);
						int minIndex = 0;
						for (int k = 1; k < j; k++) {
							int thisCost = C[i][k] + distance(k, j);
							if (thisCost < minCost) {
								minCost = thisCost;
								minIndex = k;
							}
						}
						C[i][j] = minCost;
						P[i][j] = minIndex;
					}
					else /* (i < j-1) */ {
						C[i][j] = C[i][j-1] + distance(j-1,j);
						P[i][j] = j-1;
					}					
				}
			}
		}
		
		//--------------------------------------------------------------
		// For debugging only
		//--------------------------------------------------------------
		// System.out.println("Cost table (for debugging):");
		// for (int i = 0; i < n; i++) {	// print the table
		// 	System.out.print(" " + i + ":");
		// 	for (int j = 0; j < n; j++) {
		// 		System.out.print(" " +  C[i][j] + ":" + P[i][j]);
		// 	}
		// 	System.out.println();
		// }
		//--------------------------------------------------------------

		recursiveGetPath(P, n-1, n-1);	// recursively generate path
	}

	/** Generates the optimal Doughnut path given the P matrix.
	 * 
	 *  The path is computed as follows. Our objective is to compute
	 *  the path corresponding to the entry C[n-1][n-1]. Suppose 
	 *  that in general we want to compute the path leading up to 
	 *  and arbitrary entry C[i][j]. If i >= j, we set position[i] 
	 *  = 0, and we recursively compute the path for C[P[i][j]][j]. 
	 *  If i < j, we set position[j] = 1, and we recursively compute 
	 *  path C[i][P[i][j]].
	 * 
	 */
	private static void recursiveGetPath(int[][] P, int i, int j) {
		if (i < 0 || j < 0) return;		// done with path
		if (i >= j) {					// last on outbound side
			position[i] = 0;
			recursiveGetPath(P, P[i][j], j);
		}
		else /* (i < j) */ {			// last on inbound side
			position[j] =  1;
			recursiveGetPath(P, i, P[i][j]);
		}
	}
	
	/** Generates a path by brute-force search.
	 * 
	 *  For debugging and testing, the following program generates
	 *  a path through simple brute-force search. It generates all
	 *  possible bit vectors for the elements [1..n-2], and puts
	 *  these vertices on the outbound path. The others go on the 
	 *  inbound path.
	 */
	
	private static void generatePathByBruteForce() {
		int[] p = new int[n];
		int minLength = -1;
		int nDuplicates = 0;
		for (int i = 0; i < n; i++) {
			p[i] = 0;
		}
		do {
			printPath(p);
			System.out.println("  Length = " + getLength(p));
			
			int thisLength = getLength(p);
			if (minLength < 0 || thisLength < minLength) {
				minLength = thisLength;
				for (int i = 0; i < n; i++) {
					position[i] = p[i];
				}
				nDuplicates = 1;
			}
			else if (thisLength == minLength) {
				nDuplicates++;
			}
		} while (nextPath(p));
		
		if (nDuplicates != 1) {
			System.out.println("Warning: " + nDuplicates + " duplicate solutions found");
		}
	}
	
	/** Advances to next bit vector in lexicographic order.
	 */
	
	private static boolean nextPath(int[] p) {
		int i = 1;
		while (i < n-1 && p[i] == 1) {
			p[i] = 0;
			i++;
		}
		if (i >= n-1) {
			return false;
		}
		else {
			p[i] = 1;
			return true;
		}
	
		/* ===================SOLUTION ENDS HERE=====================*/
		
		/* -------------------- END OF INSERTION --------------------*/

	}
}