1로 만들기 2

정수 X에 사용할 수 있는 연산은 다음 세 가지이다.

1. X가 3으로 나누어떨어지면 3으로 나눈다.
2. X가 2로 나누어떨어지면 2로 나눈다.
3. 1을 뺀다.

정수 N이 주어졌을 때, 위 연산 세 개를 적절히 사용해서 1을 만들려고 한다. 연산을 사용하는 횟수의 최솟값과, 그 최솟값을 달성하면서 거쳐 가는 수를 구하시오.

첫째 줄에 1보다 크거나 같고 $10^6$보다 작거나 같은 자연수 N이 주어진다.

첫째 줄에 연산을 하는 횟수의 최솟값을 출력한다.

둘째 줄에는 N을 1로 만드는 과정에서 거쳐 가는 수를 공백으로 구분해 순서대로 출력한다. 첫 수는 N이고 마지막 수는 1이다.

최솟값을 달성하는 방법이 여러 가지이면 그중 사전순으로 가장 앞서는 수열 하나만 출력한다. 최솟값을 달성하는 수열은 길이가 모두 같으므로, 두 수열을 앞에서부터 차례로 비교했을 때 처음으로 달라지는 자리에 더 작은 수가 오는 쪽이 사전순으로 앞선다.