31466번 - 초콜릿 개구리와 징검다리 스페셜 저지

문제

$N$마리의 초콜릿 개구리들이 코코랜드에서 한별랜드로 이동하려고 한다. 코코랜드와 한별랜드 사이에는 강이 하나 있으며, 초콜릿은 물에 닿으면 녹기 때문에 코코랜드에서 한별랜드로 가려면 $N$개의 징검다리를 이용해 강을 건너야 한다. 각각의 징검다리에는 1ドル$부터 $N$까지의 번호가 순서대로 붙어 있다. 편의상 코코랜드 쪽 강변을 0ドル,ドル 한별랜드 쪽 강변을 $N+1$이라고 하자.

초콜릿 개구리들도 1ドル$부터 $N$까지 번호가 붙어 있으며, 0ドル$번 지점에 아래에서 위로 $N$번부터 1ドル$번까지 순서대로 쌓여 있다. 개구리는 한 번에 한 마리만 이동할 수 있으며, 여러 마리의 개구리가 세로로 쌓여 있으면 그 중 맨 위의 개구리만 이동할 수 있다. 또한, $i$번 지점에 있던 개구리는 한 번의 이동으로 $i+1$번 또는 $i+2$번으로만 이동할 수 있으며, 뒤로 돌아갈 수는 없고, 번호가 작은 개구리 위에 번호가 큰 개구리가 올 수 없다.

한별랜드에는 결계가 쳐져 있어서, $N$번 개구리부터 1ドル$번 개구리까지 번호가 감소하는 순으로 입장하지 않으면 초콜릿 개구리에 걸린 마법이 모두 풀려 버린다. 초콜릿 개구리들은 무사히 모두 한별랜드로 갈 수 있을까?

입력

첫 번째 줄에 정수 $N$이 주어진다. $(1\le N\le 1,円 000)$

출력

초콜릿 개구리들이 모두 무사히 강을 건널 수 있다면, 첫 번째 줄에 개구리의 이동 횟수 $M$을 출력한다. 이 값은 최소일 필요는 없으나, $N(N+1)$을 초과할 수 없다.

두 번째 줄부터 $M$개의 개구리의 이동을 순서대로 한 줄에 하나씩 출력한다. $i$번 지점의 맨 위에 있는 개구리가 $j$번 지점으로 이동할 때, $i$와 $j$를 공백으로 구분하여 출력한다.

강을 건널 수 없다면, 첫 번째 줄에 -1을 출력한다.

제한

힌트