<그림 1>과 같이 정사각형 NxN 크기의 주차장이 있다.

이 주차장에는 차들이 많이 있는데 우리 차를 주차장 밖으로 빼내어야 한다.

그런데 차를 움직일 수 있는 주차관리원은 한명 뿐이다.

이 주차관리원이 하나의 차를 타고 그 차를 움직이는 것을 하나의 “작업”이라 부르기로 한다.

하나의 작업에 차는 앞뒤로 다른 차와 겹치지 않는 한 얼마든지 움직일 수 있다.

다음의 가정 하에 작업의 횟수를 가장 적게 하면서 우리 차를 주차장 밖으로 빼내기 위해서 움직여야하는 모든 차들의 순서를 계산하는 프로그램을 작성하시오.

답이 여러 가지가 나올 수 있는 경우에는 그 중 하나만 출력한다.

* 가정

1) 모든 차의 폭은 1이고 길이는 2 또는 3 이다.

2) 차는 주차되어 있는 방향에 따라 수직차(예:<그림 1>의 4번차) 수평차(예:<그림 1>의 3번차)로 구분한다. 수직차는 상하로만 수평차는 좌우로만 움직일 수 있고 회전은 할 수 없다.

3) 같은 차에 대해서 여러 번 작업할 수 있다.

4) 우리 차 외에 다른 차는 작업 도중 조금이라도 주차장 밖으로 나갈 수 없으며 우리 차가 완전히 주차장을 나가는 순간에 전체 작업은 끝난다(<그림 2>).

5) 우리 차가 수평차라면 오른쪽으로만 주차장을 나갈 수 있고 수직차이면 위쪽으로만 나갈 수 있다.

6) 입력 데이터에서 우리 차는 반드시 주차장을 빠져 나갈 수 있도록 되어 있다.

주차장 timer 1s memory 256MB

주차장 1s 256MB