레이팅 미적용Mirko는 할아버지네 다락방에서 제2차 세계대전 시절의 장난감 탱크 \(N\)대를 발견했다. 그는 곧장 친구 Slavko를 불러 함께 놀기로 했다. 둘은 전장을 만들었다. \(N\)행 \(N\)열의 칸으로 이루어진 나무판이다.
각 탱크는 한 번의 이동으로 이웃한 네 칸 중 하나로 옮길 수 있다. 탱크는 같은 행과 열의 어느 칸이든 쏠 수 있다. 탱크는 자신이 있는 행과 열을 지키고 있다고 말한다.
또한 어떤 두 탱크도 동시에 같은 칸에 있을 수 없다.
몇 시간을 놀고 두 번의 시도 끝에, Mirko의 엄마가 또 점심 먹으러 내려오라고 소리쳤고, 둘은 각 탱크가 서로 다른 행과 열을 지키도록(즉, 각 행과 각 열에 탱크가 정확히 하나씩 있도록) 탱크를 재배치하기로 했다.
다만 이 일을 최소 횟수의 이동으로 하고 싶다.
각 행과 각 열에 탱크가 하나씩 있도록 재배치하는 데 필요한 최소 이동 횟수와, 그러한 최단 이동 순서 하나를 찾는 프로그램을 작성하시오.
입력의 첫째 줄에 정수 \(N\) (\(1 \le N \le 500\))이 주어진다.
다음 \(N\)개의 줄에는 두 정수 \(R\)와 \(C\) (\(1 \le R, C \le N\))가 주어진다. 엄마가 부른 순간 탱크 한 대가 있는 행과 열이다. 같은 칸에 있는 두 탱크는 없다.
행과 열은 위에서 아래로, 왼쪽에서 오른쪽으로 \(1\)부터 \(N\)까지 번호가 붙는다.
첫째 줄에 최소 이동 횟수(이 수를 \(M\)이라 하자)를 출력한다.
다음 \(M\)개의 줄에는 이동하는 탱크와 이동 방향을 공백 하나로 구분하여 출력한다.
탱크는 입력에 주어진 순서대로 \(1\)부터 \(N\)까지 번호가 붙는다.
방향은 네 대문자 중 하나이다: 왼쪽은 L, 오른쪽은 R, 위는 U, 아래는 D.
채점
횟수 \(M\)과 이동 순서가 모두 올바르면 해당 테스트 케이스에서 만점을 받는다. 올바른 \(M\)을 출력했지만 이동 순서를 출력하지 않았거나 이동 순서가 올바르지 않으면, 해당 테스트 케이스 점수의 절반을 받는다.
| 서브태스크 | 점수 | 설명 |
|---|---|---|
Minimum number of moves | 35점 | Awards half of the points: the first line of your output (the minimum number of moves \(M\)) is correct. |
Move sequence | 35점 | Awards the other half: your move sequence is also valid — it uses exactly \(M\) moves and ends with exactly one tank guarding each row and each column. |
5
1 1
1 2
1 3
1 4
1 510
1 D
2 D
3 D
4 D
1 D
2 D
3 D
1 D
2 D
1 D5
2 3
3 2
3 3
3 4
4 38
1 R
1 R
2 U
2 U
4 D
4 D
5 L
5 L6
1 1
1 2
2 1
5 6
6 5
6 68
2 R
2 D
3 D
3 R
4 U
4 L
5 L
5 U