public Main12(){
		kattio = new Kattio(System.in, System.out);	
		N=kattio.getInt();
		path=new ArrayList<Integer>();
		if(N==0){
			return;
		}


		createCitiesList();
		if(N==1){
			path.add(0);	
		}else{
			createDistanceMatrix();
			startTime=System.nanoTime();
			Random rn = new Random();
			int startingPoint1=rn.nextInt(N);
			nearestNeighbour(startingPoint1,startTime);
			if(TWOSTARTINGPOINTS){
				int startingPoint2=rn.nextInt(N);
				while(startingPoint2==startingPoint1){
					startingPoint2=rn.nextInt(N);
				}
				nearestNeighbour(startingPoint2,startTime);
			}
//			System.out.println("before opt "+ tourDistance(path));
			path=twoOpt(path);

		}


		//printCities();
		//printDistanceMatrix();
		printPath();
//		System.out.println(tourDistance(path));

	}