시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB64219515530.754%

문제

상근이는 생일 선물로 장난감 탱크 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'로 출력한다.

정답은 여러 가지일 수도 있다.

예제 입력 1

5
1 1
1 2
1 3
1 4
1 5

예제 출력 1

10
1 D
2 D
3 D
4 D
1 D
2 D
3 D
1 D
2 D
1 D

예제 입력 2

5
2 3
3 2
3 3
3 4
4 3

예제 출력 2

8
1 R
1 R
2 U
2 U
4 D
4 D
5 L
5 L

예제 입력 3

6
1 1
1 2
2 1
5 6
6 5
6 6

예제 출력 3

8
2 R
2 D
3 D
3 R
4 U
4 L
5 L
5 U
W3sicHJvYmxlbV9pZCI6IjMwNDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWIwOWNcdWFjMTAgXHVkMGYxXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGRkXHVjNzdjIFx1YzEyMFx1YmIzY1x1Yjg1YyBcdWM3YTVcdWIwOWNcdWFjMTAgXHVkMGYxXHVkMDZjIE5cdWFjMWNcdWI5N2MgXHViYzFiXHVjNTU4XHViMmU0LiBcdWQwZjFcdWQwNmNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YjE4MFx1YWUzMCBcdWM4MDRcdWM3YTVcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWM4MDRcdWM3YTVcdWM3NDAgXHViMDk4XHViYjM0XHVkMzEwIFx1YzcwNFx1YzVkMCBOXHVkNTg5IE5cdWM1ZjQgXHVkMDZjXHVhZTMwXHViODVjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVhYzAxIFx1ZDBmMVx1ZDA2Y1x1YWMwMCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjZTc4XHVjNzQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWIxMjQgXHVjZTc4XHVjNzc0XHViMmU0LiBcdWQwZjFcdWQwNmNcdWIyOTQgXHVhYzE5XHVjNzQwIFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NDQgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVkMGYxXHVkMDZjXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzQ0IFx1YmNmNFx1ZDYzOFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHViOWQwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YjQ1MCBcdWQwZjFcdWQwNmNcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM3NzRcdWI4MDdcdWFjOGMgXHVkMGYxXHVkMDZjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWI0NTB+XHVjMTM4XHVjMmRjXHVhYzA0IFx1YjNkOVx1YzU0OCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHViMTgwXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzViNFx1YmEzOFx1YjJjOFx1YjI5NCBcdWM4MTBcdWMyZWNcdWFlNGNcdWM5YzAgXHVhYzcwXHViOTc0XHViYTc0XHVjMTFjIFx1YjE4MFx1YWNlMFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWI5N2MgXHViYWJiXHViOWM4XHViNTQ1XHVkNTU4XHVhYzhjIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YWNlMCwgXHViMmY5XHVjN2E1IFx1YzgxMFx1YzJlY1x1Yzc0NCBcdWJhMzlcdWM3M2NcdWI3ZWMgXHVjNjI0XHViNzdjXHVhY2UwIFx1YzE4Y1x1YjlhY1x1Y2NlNFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDBmMVx1ZDA2Y1x1YWMwMCBcdWJhYThcdWI0ZTAgXHVkNTg5XHVhY2ZjIFx1YzVmNFx1Yzc0NCBcdWJjZjRcdWQ2MzhcdWQ1NThcdWFjOGMgXHViYzMwXHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiYyBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjODEwXHVjMmVjXHVjNzQ0IFx1YmEzOVx1YzczY1x1YjdlYyBcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiAoXHVjOTg5LCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNTg5XHVhY2ZjIFx1YzVmNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM3NTggXHVkMGYxXHVkMDZjXHViOWNjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlx1Yzc3NFx1YjgwN1x1YWM4YyBcdWJjMzBcdWNlNThcdWI5N2MgXHViYzE0XHVhZmI4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWQwZjFcdWQwNmNcdWI5N2MgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM4MDFcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVkMGYxXHVkMDZjXHViOTdjIFx1YmE4NyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0LCBcdWFjMDEgXHVkNTg5XHVhY2ZjIFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMGYxXHVkMDZjXHVhYzAwIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWI0MThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yjc3Y1x1YmE3NCBcdWQwZjFcdWQwNmNcdWI5N2MgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1ZDY5Zlx1YzIxOFx1YWMwMCBcdWFjMDBcdWM3YTUgXHVjNzkxXHVjNzQwIFx1YWM4M1x1Yzc0NCBcdWNjM2VcdWIyOTRcdWIyZTQuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDBmMVx1ZDA2Y1x1Yzc1OCBcdWMyMTggTlx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICg1ICZsZTsgTiAmbGU7IDUwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE5cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YWMwMSBcdWQwZjFcdWQwNmNcdWFjMDAgXHVjNzg4XHViMjk0IFx1ZDU4OVx1Yzc1OCBcdWJjODhcdWQ2MzggUlx1YWNmYyBcdWM1ZjRcdWM3NTggXHViYzg4XHVkNjM4IENcdWFjMDAgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMSAmbGU7IFIsIEMgJmxlOyBOKSBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzQwIDFcdWJkODBcdWQxMzAgTlx1YWU0Y1x1YzljMCBcdWJjODhcdWQ2MzhcdWFjMDAgXHViOWU0XHVhY2E4XHVjODM4IFx1Yzc4OFx1YzczY1x1YmE3MCwgXHVjNzA0XHVjNWQwXHVjMTFjIFx1YzU0NFx1Yjc5OCwgXHVjNjdjXHVjYWJkXHVjNWQwXHVjMTFjIFx1YzYyNFx1Yjk3OFx1Y2FiZCBcdWMyMWNcdWMxMWNcdWM3NzRcdWIyZTQuIFx1YjQ1MCBcdWQwZjFcdWQwNmNcdWFjMDAgXHVhYzE5XHVjNzQwIFx1Y2U3OFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVhY2JkXHVjNmIwXHViMjk0IFx1YzVjNlx1YjJlNC48XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5cdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1ZDBmMVx1ZDA2Y1x1Yjk3YyBcdWJhODcgXHViYzg4IFx1Yzc3NFx1YjNkOVx1YzJkY1x1ZDBhNFx1YmE3NCBcdWI0MThcdWIyOTRcdWM5YzBcdWI5N2MgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQ0IEtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgS1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjNWI0XHViNWE0IFx1ZDBmMVx1ZDA2Y1x1Yjk3YyBcdWM1YjRcdWIyOTAgXHViYzI5XHVkNWE1XHVjNzNjXHViODVjIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NFx1YzljMCBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1YWMwMFx1YzdhNSBcdWJhM2NcdWM4MDAgXHVjOGZjXHVjNWI0XHVjOWMwXHViMjk0IFx1ZDBmMVx1ZDA2Y1x1Yzc1OCBcdWJjODhcdWQ2MzhcdWIyOTQgMVx1YmM4OFx1Yzc3NFx1YWNlMCwgXHViMDk4XHViYTM4XHVjOWMwIFx1ZDBmMVx1ZDA2Y1x1YjI5NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgMiwgMywgLi4uLCBOXHViYzg4XHVjNzc0XHViMmU0LiBcdWJjMjlcdWQ1YTVcdWM3NDAgXHVjNjdjXHVjYWJkXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOVx1ZDU2MCBcdWI1NGNcdWIyOTQgJiMzOTtMJiMzOTssIFx1YzYyNFx1Yjk3OFx1Y2FiZFx1Yzc0MCAmIzM5O1ImIzM5OywgXHVjNzA0XHViMjk0ICYjMzk7VSYjMzk7LCBcdWM1NDRcdWI3OThcdWIyOTQgJiMzOTtEJiMzOTtcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWM4MTVcdWIyZjVcdWM3NDAgXHVjNWVjXHViN2VjIFx1YWMwMFx1YzljMFx1Yzc3YyBcdWMyMThcdWIzYzQgXHVjNzg4XHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJodG1sX3RpdGxlIjoiMCIsInByb2JsZW1fbGFuZ190Y29kZSI6IktvcmVhbiJ9LHsicHJvYmxlbV9pZCI6IjMwNDMiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJURU5LSUNJIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyBmb3VuZCBhIGNvbGxlY3Rpb24gb2YgTiB0b3kgdGFua3MgZGF0aW5nIGJhY2sgdG8gdGhlIFNlY29uZCBXb3JsZCBXYXIgb24gaGlzIGdyYW5kZmF0aGVyJiMzOTtzIGF0dGljLiBIZSBwcm9tcHRseSBjYWxsZWQgaGlzIGZyaWVuZCBTbGF2a28gdG8gcGxheSB3aXRoIGhpbS4gVGhleSBtYWRlIGEgYmF0dGxlZmllbGQgJm5kYXNoOyBhIHdvb2RlbiBib2FyZCBjb25zaXN0aW5nIG9mIHNxdWFyZXMgaW4gTiByb3dzIGFuZCBOIGNvbHVtbnMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggdGFuayBjYW4gYmUgbW92ZWQgdG8gb25lIG9mIHRoZSBmb3VyIG5laWdoYm91cmluZyBzcXVhcmVzIGluIGEgc2luZ2xlIG1vdmUuIEEgdGFuayBjYW4gc2hvb3QgYXQgYW55IHNxdWFyZSBpbiB0aGUgc2FtZSByb3cgYW5kIGNvbHVtbi4gVGhlIHRhbmsgaXMgc2FpZCB0byBiZSBndWFyZGluZyB0aGUgcm93IGFuZCBjb2x1bW4gaXQgaXMgaW4uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFkZGl0aW9uYWxseSwgbm8gdHdvIHRhbmtzIGNhbiBiZSBpbiB0aGUgc2FtZSBzcXVhcmUgYXQgYW55IHRpbWUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkFmdGVyIG1hbnkgaG91cnMgb2YgcGxheSBhbmQgdHdvIHByZXZpb3VzIGF0dGVtcHRzLCBNaXJrbyYjMzk7cyBtb20geWVsbGVkIGF0IHRoZW0gdG8gY29tZSBkb3duIGZvciBsdW5jaCBhZ2FpbiwgYW5kIHRoZXkgZGVjaWRlZCB0byByZWFycmFuZ2UgdGhlIHRhbmtzIHNvIHRoYXQgZWFjaCB0YW5rIGd1YXJkcyBhIGRpZmZlcmVudCByb3cgYW5kIGNvbHVtbiAobWVhbmluZyBhbHNvIHRoYXQgZWFjaCByb3cgYW5kIGNvbHVtbiBjb250YWlucyBvbmx5IG9uZSB0YW5rKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+SG93ZXZlciwgdGhleSB3YW50IHRvIGRvIHRoaXMgdXNpbmcgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Xcml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgcmVxdWlyZWQgdG8gcmVhcnJhbmdlIHRoZSB0YW5rcyBzbyB0aGF0IGVhY2ggcm93IGFuZCBlYWNoIGNvbHVtbiBjb250YWlucyBhIHNpbmdsZSB0YW5rLCBhbmQgb25lIHN1Y2ggc2hvcnRlc3Qgc2VxdWVuY2Ugb2YgbW92ZXMuJm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0aGUgaW50ZWdlciBOICg1ICZsZTsgTiAmbGU7IDUwMCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIGZvbGxvd2luZyBOIGxpbmVzIGNvbnRhaW5zIHR3byBpbnRlZ2VycyBSIGFuZCBDICgxICZsZTsgUiwgUyAmbGU7IE4pLCB0aGUgcm93IGFuZCBjb2x1bW4gb2YgYSBzaW5nbGUgdGFuayBhdCB0aGUgbW9tZW50IG9mIG1vbSYjMzk7cyBjYWxsLiBObyB0d28gdGFua3MgYXJlIG9uIHRoZSBzYW1lIHNxdWFyZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Um93cyBhbmQgY29sdW1ucyBhcmUgbWFya2VkIDEgdGhyb3VnaCBOLCB0b3AtZG93biBhbmQgbGVmdC10by1yaWdodC4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIChjYWxsIHRoaXMgbnVtYmVyIEspIG9uIHRoZSBmaXJzdCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IEsgbGluZXMgc2hvdWxkIGNvbnRhaW4gdGhlIHRhbmsgYmVpbmcgbW92ZWQgYW5kIHRoZSBkaXJlY3Rpb24gaXQgaXMgbW92ZWQgaW4sIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+VGFua3MgYXJlIG51bWJlcmVkIDEgdGhyb3VnaCBOLCBpbiB0aGUgb3JkZXIgaW4gd2hpY2ggdGhleSBhcmUgZ2l2ZW4gaW4gdGhlIGlucHV0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5UaGUgZGlyZWN0aW9uIGNhbiBiZSBvbmUgb2YgZm91ciB1cHBlcmNhc2UgbGV0dGVyczogJiMzOTtMJiMzOTsgZm9yIGxlZnQsICYjMzk7UiYjMzk7IGZvciByaWdodCwgJiMzOTtVJiMzOTsgZm9yIHVwIGFuZCAmIzM5O0QmIzM5OyBmb3IgZG93bi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Tm90ZTogVGhlIHNlcXVlbmNlIG5lZWQgbm90IGJlIHVuaXF1ZS4mbmJzcDs8XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwiaHRtbF90aXRsZSI6IjAiLCJwcm9ibGVtX2xhbmdfdGNvZGUiOiJFbmdsaXNoIn1d

출처

Contest > Croatian Open Competition in Informatics > COCI 2006/2007 > Contest #3 4번