21873번 - 개구리 징검다리 건너기 스페셜 저지출처분류

서대문구에 있는 한 연못에 $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를 출력한다.