import java.util.Scanner;
import java.util.*;

public class Hanoi {
	@SuppressWarnings("unchecked")
	public static void main(String[] args) {
		System.out.println("How Many Disks?");
		Scanner in = new Scanner(System.in);
		int n = in.nextInt();
		Stack<Integer> fullStack = new Stack<>();
		for (int i = n; i > 0; i--) {
			fullStack.push(i);
		}
		Vertex start = new Vertex((Stack<Integer>) fullStack.clone(), new Stack<Integer>(), new Stack<Integer>());
		Vertex end = new Vertex(new Stack<Integer>(), new Stack<Integer>(), (Stack<Integer>) fullStack.clone());
		printSolution(start, end);
	}

	public static void printSolution(Vertex start, Vertex end) {
		List<Vertex> solutionString = bfs(start, end);
		Collections.reverse(solutionString);
		for (Vertex state : solutionString) {
			System.out.println(state);
		}
		System.out.println("Total Moves: " + (solutionString.size() - 1));
	}

	public static List<Vertex> bfs(Vertex start, Vertex end) {
		Queue<Vertex> path = new LinkedList<>();
		Set<Vertex> hasVisited = new HashSet<>();
		List<Vertex> solution = new ArrayList<>();
		Vertex temp = start;
		path.offer(temp);
		hasVisited.add(temp);
		while (!temp.equals(end) && !path.isEmpty()) {
			temp = path.poll();
			for (Vertex n : temp.getChildren()) {
				if (!hasVisited.contains(n)) {
					path.offer(n);
					hasVisited.add(n);
				}
			}

		}
		for (Vertex vertex = temp; vertex != null; vertex = vertex.previous) {
			solution.add(vertex);
		}
		return solution;
	}
}