22872번 - 공 옮기기 스페셜 저지전체 채점

문제

1ドル$ 번 부터 $N$ 번까지의 번호가 붙어있는 $N$ 개의 공이 있다. 그리고 1ドル$ 번부터 3ドル$ 번까지의 번호가 붙어 있는 바구니가 있다. 처음에는 1ドル$ 번 바구니에 $N$ 개의 공이 담겨있다.

다음과 같은 규칙으로 한 바구니에서 다른 바구니로 공을 옮길 수 있다.

• 바구니에 들어있는 공들을 번호 순으로 나열했을 때, 가운데에 오는 공을 중심 공이라고 한다.
  • 공의 개수가 짝수이면, 가운데에 오는 두 개의 공 중에 번호가 큰 공이 중심 공이다.
• $a$ 번 바구니에서 $b$ 번 바구니로 공을 옮길 때는 $a$ 번 바구니의 중심 공을 $b$ 번 바구니로 옮겨야 하고, 옮긴 공은 $b$ 번 바구니의 중심 공이 되어야 한다.

해당 규칙을 통해 1ドル$ 번 바구니에 있는 공 $N$ 개 모두를 3ドル$ 번 바구니로 공을 옮기는 과정을 출력하자.

입력

첫째 줄에 공의 개수 $N$이 주어진다. (1ドル \le N \le 26$)

출력

첫째 줄에 공을 옮기는 횟수 $M$을 출력한다. (1ドル \le M \le 980,403円$)

다음 $M$ 개의 줄의 $i$ 번째 줄에는 두 정수 $a,ドル $b$를 공백으로 구분하여 출력한다. (1ドル \le a, b \le 3; a \ne b$) 이는 $i$번째 연산이 문제의 규칙에 따라 $a$ 번 바구니에서 공을 $b$ 번 바구니로 옮긴다는 뜻이다.

출력이 끝난 이후에 1ドル$ 번 바구니에 있는 모든 공이 3ドル$ 번 바구니로 이동해야 한다.

제한

힌트