시간 제한메모리 제한제출정답맞은 사람정답 비율
1 초 512 MB79191756.667%

문제

체스판의 세계에는 귀여운 백마인 백남이가 살고 있다. 백남이는 방학을 맞아 체스판 여행을 떠나려고 한다.

백남이가 생각 중인 계획은 다음과 같은 규칙을 따른다.

  • 체스판의 총 크기는 $N\times N$이다.
  • 체스판에 있는 모든 칸을 방문해야 한다.
  • 같은 칸을 여러 번 방문할 수 있다. 하지만 칸을 방문한 총 횟수는 $2N^2$ 이하여야 한다.
  • 백남이가 이동하는 방법의 수는 8가지이며, 다음과 같다.


 

MBTI가 N(직관형)인 백남이는 모든 계획을 짜지 않고는 여행을 시작할 수 없다!

계획 수립에 골머리를 앓고 있는 백남이를 도와 백남이의 여행 계획을 짜주자!


 

입력

첫 줄에 격자판의 행의 수이자 열의 수인 $N$ 이 주어진다. ($1\leq N \leq 500$)

둘째 줄에는 현재 백남이의 좌표를 나타내는 정수 r, c가 주어진다. 이는 r번째 행, c번째 열에 위치한 칸을 의미한다.

출력

만약 여행이 불가능하다고 판단되면, -1을 출력하고,

여행이 가능하면, 첫째 줄에 칸을 방문한 총 횟수 $K$를 출력하고, 이후 $K$개의 줄에 한 줄에 하나씩 백남이가 방문한 칸의 좌표를 차례대로 출력한다.

예제 입력 1

5
1 1

예제 출력 1

25
1 1
3 2
5 1
4 3
5 5
3 4
1 5
2 3
4 2
2 1
1 3
2 5
4 4
5 2
3 1
1 2
2 4
4 5
5 3
4 1
2 2
1 4
3 3
5 4
3 5

예제 입력 2

3
2 2

예제 출력 2

-1

출처

University > 충남대학교 > 제5회 생각하는 프로그래밍 대회  F번