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));
	}
	
	/** 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 ---------------------*/
		



		
		/* -------------------- END OF INSERTION --------------------*/

	}
}