시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1.2 초 (추가 시간 없음) 1024 MB 84 57 33 71.739%

문제

서대문구에 있는 한 연못에 $N$마리의 하얀 개구리와 $N$마리의 검은 개구리가 $2N+1$개의 연꽃으로 이루어진 징검다리를 건너려고 하고 있다. 그림에서 보이는 것과 같이 각 무리의 개구리들에는 앞에서부터 $1$부터 $N$까지 번호가 붙어있다. 각 무리의 개구리들은 징검다리를 건너서 서로 반대쪽으로 지나가려고 하고 있다. 그러나 바쁜 일이 있는 개구리들은 서로 먼저 지나가라고 양보하기 어려운 상황이었기 때문에 모두 동시에 징검다리를 건너려고 한다.

개구리들은 다음과 같이 이동할 수 있다.

  • 하얀 개구리들은 오른쪽으로만, 검은 개구리들은 왼쪽으로만 움직인다.
  • 한 번에 한 마리의 개구리만 움직일 수 있다.
  • 자신의 진행 방향 바로 앞에 있는 연꽃이 비어있는 경우, 진행 방향으로 한 칸 이동할 수 있다.
  • 자신의 진행 방향 바로 앞에 있는 연꽃에 자신의 색과 다른 개구리가 있는 경우, 그 개구리 한 마리를 건너뛰어서 두 칸 이동할 수 있다.
  • 자신의 진행 방향 앞에 있는 두 개 이상의 연꽃이 비어있다고 하더라도 한 번에 두 칸 이상 이동할 수 없다.
  • 두 마리 이상의 개구리를 뛰어넘거나, 자신의 색과 같은 색의 개구리를 뛰어넘을 수 없다.

위의 규칙에 따라 각 개구리를 움직여서 그림과 같이 개구리들이 반대편에 도달할 수 있도록 하여라.

입력

각 무리에 있는 개구리의 수 $N$이 주어진다. ($1 \le N \le 1\,000$)

출력

첫 번째 줄에 개구리들을 움직여야 하는 횟수 $M$을 출력한다. 단, $M$은 $1\,500\,000$을 넘어서는 안된다.

두 번째 줄부터 $M$개의 줄에 걸쳐서 움직인 개구리의 정보를 순서대로 출력한다. $p$번째 하얀 개구리가 움직인 경우 1 p를 출력하고, $p$번째 검은 개구리가 움직인 경우 2 p를 출력한다.

예제 입력 1

1

예제 출력 1

3
1 1
2 1
1 1