장난감 탱크

상근이는 생일 선물로 장난감 탱크 N개를 받았다. 그는 나무판 위에 N행 N열 크기의 전장을 만들고, 각 탱크를 서로 다른 칸에 놓았다.

탱크 하나는 한 번 움직일 때 현재 칸과 인접한 네 칸 중 하나로 이동할 수 있다. 또한 탱크는 자신이 있는 행과 열 전체를 공격할 수 있으므로, 그 행과 열을 보호한다고 볼 수 있다.

두 탱크가 동시에 같은 칸에 있을 수는 없다.

상근이는 점심을 먹으러 가기 전에 모든 행과 모든 열이 정확히 하나의 탱크로 보호되도록 배치를 바꾸려고 한다. 즉, 최종 배치에서는 각 행에 탱크가 하나씩 있고, 각 열에도 탱크가 하나씩 있어야 한다.

필요한 이동 횟수가 최소가 되도록 탱크들을 움직이는 방법을 구하시오.

첫째 줄에 탱크의 수 N이 주어진다. (5 <= N <= 500)

다음 N개의 줄에는 각 탱크가 있는 행 번호 R과 열 번호 C가 주어진다. (1 <= R, C <= N) 행과 열은 각각 위에서 아래, 왼쪽에서 오른쪽 순서로 1부터 N까지 번호가 매겨져 있다.

입력에서 두 탱크가 같은 칸에 있는 경우는 없다.

첫째 줄에 필요한 최소 이동 횟수 K를 출력한다.

다음 K개의 줄에는 이동할 탱크의 번호와 방향을 출력한다. 입력에서 처음 주어진 탱크가 1번이고, 이후 탱크는 순서대로 2, 3, ..., N번이다.

방향은 왼쪽으로 이동할 때 L, 오른쪽으로 이동할 때 R, 위로 이동할 때 U, 아래로 이동할 때 D를 출력한다.

정답이 여러 가지라면 그중 아무 것이나 출력해도 된다.