컵 쌓기(Stacking Cup) timer 1000초 memory 64MB

다양한 크기의 컵 N개와 A, B, C 3개의 쟁반이 있다. 

처음에 컵들이 쟁반에 거꾸로 쌓여있는데, 각 쟁반에 있는 컵은 가장 작은 컵이 아래에 있고, 그다음 두 번째로 작은 것, 그다음 세 번째로 작은 것 등..

예를 들어, 그림 1은 N=5 이고 2개의 컵은 쟁반 A에, B에는 아무것도 없고, C에는 3개가 있다.

 처음 쟁반의 상태가 주어지면, 모든 컵들을 이동하여 쟁반 A나 C에 쌓을 수 있다.

컵을 이동할 때는 다음의 세 가지 규칙을 따른다.

• 규칙 1. 쟁반의 컵은 가장 위에 있는 컵만 다른 쟁반의 가장 위에 있는 컵 위에 쌓을 수 있다.

• 규칙 2. 큰 컵 위에 작은 컵은 쌓을 수 없다.

• 규칙 3. A에서 C, C에서 A로는 직접 이동할 수 없다.

따라서 직접 이동 가능한 것은 A에서 B, B에서 A, B에서 C, C에서 B 중 하나이다.

당신이 할 일은 N개의 컵과 정수 M이 주어질 때 쟁반 A에 M번 안에 모든 컵들을 쌓을 수 있는지를 결정하는 것이다.

가능하다면 최소 이동 횟수를 출력하고, 그렇지 않으면 -1을 출력한다.