26220번 - 겨울 숲의 썰매 트랙 스페셜 저지

당신은 겨울 숲에 썰매 트랙을 만들고 있다. 썰매 트랙은 크기 $N \times N$의 격자 영역 내에 $1 \times 1$ 크기의 다음 두 가지 타일을 놓아 만들 수 있으며, 각각 길이 없는 타일과 길이 있는 타일을 나타낸다.

썰매 트랙의 규칙은 다음과 같다.

1. 하나의 썰매 트랙은 길이 있는 타일들로만 구성된다.
2. 타일은 회전해서 놓을 수 있다.
3. 타일의 길은 인접한 다른 타일의 길과 이어져 있어야 한다. 격자판 밖으로 길이 나가거나 길이 끊기면 안 된다.

$N$이 $3$ 이상의 홀수일 경우 조건을 만족하는 썰매 트랙은 항상 존재한다.

썰매 트랙의 타일 중 하나를 시작 타일로 정했을 때, 썰매 트랙의 길이를 시작 타일에서 트랙의 길을 따라서 시작 타일로 돌아오기까지 방문한 서로 다른 타일의 수라고 하자.

가장 긴 썰매 트랙을 만들려면 어떻게 해야 할까?

첫째 줄에 영역의 크기를 나타내는 홀수 $N$ ($3 \leq N \leq 999$)이 주어진다.

가장 긴 썰매 트랙에 대해서 그 트랙의 길이 $K$를 출력한다.

다음 줄에는 시작 타일의 좌표가 $r$행 $c$열일때 $r$과 $c$를 출력한다. 가능한 시작 타일이 여러 개일 경우 그 중 아무거나 출력한다. 좌표는 $1$부터 시작한다.

그 다음 줄에는 선택한 시작 타일에서부터 트랙의 길을 따라서 그 타일으로 돌아오기까지의 이동 방향을 알파벳 대문자로 출력한다. 가로로 $1$ 이동은 R, 가로로 $-1$ 이동은 L, 세로로 $1$ 이동은 D, 세로로 $-1$ 이동은 U로 출력한다.

가능한 트랙이 여러 가지일 경우 그 중 아무거나 출력한다.