시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 116 28 27 26.214%

문제

상근이는 생일 선물로 장난감 탱크 N개를 받았다. 탱크를 가지고 놀기 전장을 만들었다. 전장은 나무판 위에 N행 N열 크기로 만들었다.

각 탱크가 한 번에 움직일 수 칸은 인접한 네 칸이다. 탱크는 같은 행과 열에 있는 모든 칸을 공격할 수 있다. 따라서, 탱크는 자신이 있는 칸에 해당하는 행과 열을 보호하고 있다고 말할 수 있다.

두 탱크가 동시에 같은 정사각형 안에 있을 수는 없다.

이렇게 탱크를 가지고 두~세시간 동안 열심히 놀고 있었다. 상근이의 어머니는 점심까지 거르면서 놀고있는 상근이를 못마땅하게 생각했고, 당장 점심을 먹으러 오라고 소리쳤다. 상근이는 탱크가 모든 행과 열을 보호하게 배치를 바꾼 다음에 점심을 먹으러 가려고 한다. (즉, 각각의 행과 열에 하나의 탱크만 있어야 한다)

이렇게 배치를 바꾸는 경우에 탱크를 움직이는 횟수를 적게 하려고 한다.

탱크를 몇 번 움직이면, 각 행과 열에 있는 탱크가 하나가 되는지 구하는 프로그램을 작성하시오. 움직이는 방법이 여러가지라면 탱크를 움직이는 횟수가 가장 작은 것을 찾는다.

입력

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

다음 N개 줄에는 각 탱크가 있는 행의 번호 R과 열의 번호 C가 주어진다. (1 ≤ R, S ≤ 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
W3sicHJvYmxlbV9pZCI6IjMwNDMiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3YTVcdWIwOWNcdWFjMTAgXHVkMGYxXHVkMDZjIiwiZGVzY3JpcHRpb24iOiI8cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHVjMGRkXHVjNzdjIFx1YzEyMFx1YmIzY1x1Yjg1YyBcdWM3YTVcdWIwOWNcdWFjMTAgXHVkMGYxXHVkMDZjIE5cdWFjMWNcdWI5N2MgXHViYzFiXHVjNTU4XHViMmU0LiBcdWQwZjFcdWQwNmNcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YjE4MFx1YWUzMCBcdWM4MDRcdWM3YTVcdWM3NDQgXHViOWNjXHViNGU0XHVjNWM4XHViMmU0LiBcdWM4MDRcdWM3YTVcdWM3NDAgXHViMDk4XHViYjM0XHVkMzEwIFx1YzcwNFx1YzVkMCBOXHVkNTg5IE5cdWM1ZjQgXHVkMDZjXHVhZTMwXHViODVjIFx1YjljY1x1YjRlNFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVhYzAxIFx1ZDBmMVx1ZDA2Y1x1YWMwMCBcdWQ1NWMgXHViYzg4XHVjNWQwIFx1YzZjMFx1YzljMVx1Yzc3YyBcdWMyMTggXHVjZTc4XHVjNzQwIFx1Yzc3OFx1YzgxMVx1ZDU1YyBcdWIxMjQgXHVjZTc4XHVjNzc0XHViMmU0LiBcdWQwZjFcdWQwNmNcdWIyOTQgXHVhYzE5XHVjNzQwIFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM1ZDAgXHVjNzg4XHViMjk0IFx1YmFhOFx1YjRlMCBcdWNlNzhcdWM3NDQgXHVhY2Y1XHVhY2E5XHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVkMGYxXHVkMDZjXHViMjk0IFx1Yzc5MFx1YzJlMFx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjZTc4XHVjNWQwIFx1ZDU3NFx1YjJmOVx1ZDU1OFx1YjI5NCBcdWQ1ODlcdWFjZmMgXHVjNWY0XHVjNzQ0IFx1YmNmNFx1ZDYzOFx1ZDU1OFx1YWNlMCBcdWM3ODhcdWIyZTRcdWFjZTAgXHViOWQwXHVkNTYwIFx1YzIxOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjQ1MCBcdWQwZjFcdWQwNmNcdWFjMDAgXHViM2Q5XHVjMmRjXHVjNWQwIFx1YWMxOVx1Yzc0MCBcdWM4MTVcdWMwYWNcdWFjMDFcdWQ2MTUgXHVjNTQ4XHVjNWQwIFx1Yzc4OFx1Yzc0NCBcdWMyMThcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWM3NzRcdWI4MDdcdWFjOGMgXHVkMGYxXHVkMDZjXHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWI0NTB+XHVjMTM4XHVjMmRjXHVhYzA0IFx1YjNkOVx1YzU0OCBcdWM1ZjRcdWMyZWNcdWQ3ODggXHViMTgwXHVhY2UwIFx1Yzc4OFx1YzVjOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHVjNzU4IFx1YzViNFx1YmEzOFx1YjJjOFx1YjI5NCBcdWM4MTBcdWMyZWNcdWFlNGNcdWM5YzAgXHVhYzcwXHViOTc0XHViYTc0XHVjMTFjIFx1YjE4MFx1YWNlMFx1Yzc4OFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWI5N2MgXHViYWJiXHViOWM4XHViNTQ1XHVkNTU4XHVhYzhjIFx1YzBkZFx1YWMwMVx1ZDU4OFx1YWNlMCwgXHViMmY5XHVjN2E1IFx1YzgxMFx1YzJlY1x1Yzc0NCBcdWJhMzlcdWM3M2NcdWI3ZWMgXHVjNjI0XHViNzdjXHVhY2UwIFx1YzE4Y1x1YjlhY1x1Y2NlNFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDBmMVx1ZDA2Y1x1YWMwMCBcdWJhYThcdWI0ZTAgXHVkNTg5XHVhY2ZjIFx1YzVmNFx1Yzc0NCBcdWJjZjRcdWQ2MzhcdWQ1NThcdWFjOGMgXHViYzMwXHVjZTU4XHViOTdjIFx1YmMxNFx1YWZiYyBcdWIyZTRcdWM3NGNcdWM1ZDAgXHVjODEwXHVjMmVjXHVjNzQ0IFx1YmEzOVx1YzczY1x1YjdlYyBcdWFjMDBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LiAoXHVjOTg5LCBcdWFjMDFcdWFjMDFcdWM3NTggXHVkNTg5XHVhY2ZjIFx1YzVmNFx1YzVkMCBcdWQ1NThcdWIwOThcdWM3NTggXHVkMGYxXHVkMDZjXHViOWNjIFx1Yzc4OFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQpPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1Yzc3NFx1YjgwN1x1YWM4YyBcdWJjMzBcdWNlNThcdWI5N2MgXHViYzE0XHVhZmI4XHViMjk0IFx1YWNiZFx1YzZiMFx1YzVkMCBcdWQwZjFcdWQwNmNcdWI5N2MgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1ZDY5Zlx1YzIxOFx1Yjk3YyBcdWM4MDFcdWFjOGMgXHVkNTU4XHViODI0XHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHVkMGYxXHVkMDZjXHViOTdjIFx1YmE4NyBcdWJjODggXHVjNmMwXHVjOWMxXHVjNzc0XHViYTc0LCBcdWFjMDEgXHVkNTg5XHVhY2ZjIFx1YzVmNFx1YzVkMCBcdWM3ODhcdWIyOTQgXHVkMGYxXHVkMDZjXHVhYzAwIFx1ZDU1OFx1YjA5OFx1YWMwMCBcdWI0MThcdWIyOTRcdWM5YzAgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1YzZjMFx1YzljMVx1Yzc3NFx1YjI5NCBcdWJjMjlcdWJjOTVcdWM3NzQgXHVjNWVjXHViN2VjXHVhYzAwXHVjOWMwXHViNzdjXHViYTc0IFx1ZDBmMVx1ZDA2Y1x1Yjk3YyBcdWM2YzBcdWM5YzFcdWM3NzRcdWIyOTQgXHVkNjlmXHVjMjE4XHVhYzAwIFx1YWMwMFx1YzdhNSBcdWM3OTFcdWM3NDAgXHVhYzgzXHVjNzQ0IFx1Y2MzZVx1YjI5NFx1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGYxXHVkMDZjXHVjNzU4IFx1YzIxOCBOXHVjNzc0IFx1YzhmY1x1YzViNFx1YzljNFx1YjJlNC4gKDUgJmxlOyBOICZsZTsgNTAwKTxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgTlx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVhYzAxIFx1ZDBmMVx1ZDA2Y1x1YWMwMCBcdWM3ODhcdWIyOTQgXHVkNTg5XHVjNzU4IFx1YmM4OFx1ZDYzOCBSXHVhY2ZjIFx1YzVmNFx1Yzc1OCBcdWJjODhcdWQ2MzggQ1x1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgxICZsZTsgUiwgUyAmbGU7IE4pIFx1ZDU4OVx1YWNmYyBcdWM1ZjRcdWM3NDAgMVx1YmQ4MFx1ZDEzMCBOXHVhZTRjXHVjOWMwIFx1YmM4OFx1ZDYzOFx1YWMwMCBcdWI5ZTRcdWFjYThcdWM4MzggXHVjNzg4XHVjNzNjXHViYTcwLCBcdWM3MDRcdWM1ZDBcdWMxMWMgXHVjNTQ0XHViNzk4LCBcdWM2N2NcdWNhYmRcdWM1ZDBcdWMxMWMgXHVjNjI0XHViOTc4XHVjYWJkIFx1YzIxY1x1YzExY1x1Yzc3NFx1YjJlNC4gXHViNDUwIFx1ZDBmMVx1ZDA2Y1x1YWMwMCBcdWFjMTlcdWM3NDAgXHVjZTc4XHVjNWQwIFx1Yzc4OFx1YjI5NCBcdWFjYmRcdWM2YjBcdWIyOTQgXHVjNWM2XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVkMGYxXHVkMDZjXHViOTdjIFx1YmE4NyBcdWJjODggXHVjNzc0XHViM2Q5XHVjMmRjXHVkMGE0XHViYTc0IFx1YjQxOFx1YjI5NFx1YzljMFx1Yjk3YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuIFx1Yzc3NCBcdWFjMTJcdWM3NDQgS1x1Yjc3Y1x1YWNlMCBcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBLXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWM1YjRcdWI1YTQgXHVkMGYxXHVkMDZjXHViOTdjIFx1YzViNFx1YjI5MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0XHVjOWMwIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVhYzAwXHVjN2E1IFx1YmEzY1x1YzgwMCBcdWM4ZmNcdWM1YjRcdWM5YzBcdWIyOTQgXHVkMGYxXHVkMDZjXHVjNzU4IFx1YmM4OFx1ZDYzOFx1YjI5NCAxXHViYzg4XHVjNzc0XHVhY2UwLCBcdWIwOThcdWJhMzhcdWM5YzAgXHVkMGYxXHVkMDZjXHViMjk0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyAyLCAzLCAuLi4sIE5cdWJjODhcdWM3NzRcdWIyZTQuIFx1YmMyOVx1ZDVhNVx1Yzc0MCBcdWM2N2NcdWNhYmRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5XHVkNTYwIFx1YjU0Y1x1YjI5NCAmIzM5O0wmIzM5OywgXHVjNjI0XHViOTc4XHVjYWJkXHVjNzQwICYjMzk7UiYjMzk7LCBcdWM3MDRcdWIyOTQgJiMzOTtVJiMzOTssIFx1YzU0NFx1Yjc5OFx1YjI5NCAmIzM5O0QmIzM5O1x1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzgxNVx1YjJmNVx1Yzc0MCBcdWM1ZWNcdWI3ZWMgXHVhYzAwXHVjOWMwXHVjNzdjIFx1YzIxOFx1YjNjNCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA0MyIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IlRFTktJQ0kiLCJkZXNjcmlwdGlvbiI6IjxwPk1pcmtvIGZvdW5kIGEgY29sbGVjdGlvbiBvZiBOIHRveSB0YW5rcyBkYXRpbmcgYmFjayB0byB0aGUgU2Vjb25kIFdvcmxkIFdhciBvbiBoaXMgZ3JhbmRmYXRoZXImIzM5O3MgYXR0aWMuIEhlIHByb21wdGx5IGNhbGxlZCBoaXMgZnJpZW5kIFNsYXZrbyB0byBwbGF5IHdpdGggaGltLiBUaGV5IG1hZGUgYSBiYXR0bGVmaWVsZCAmbmRhc2g7IGEgd29vZGVuIGJvYXJkIGNvbnNpc3Rpbmcgb2Ygc3F1YXJlcyBpbiBOIHJvd3MgYW5kIE4gY29sdW1ucy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCB0YW5rIGNhbiBiZSBtb3ZlZCB0byBvbmUgb2YgdGhlIGZvdXIgbmVpZ2hib3VyaW5nIHNxdWFyZXMgaW4gYSBzaW5nbGUgbW92ZS4gQSB0YW5rIGNhbiBzaG9vdCBhdCBhbnkgc3F1YXJlIGluIHRoZSBzYW1lIHJvdyBhbmQgY29sdW1uLiBUaGUgdGFuayBpcyBzYWlkIHRvIGJlIGd1YXJkaW5nIHRoZSByb3cgYW5kIGNvbHVtbiBpdCBpcyBpbi4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWRkaXRpb25hbGx5LCBubyB0d28gdGFua3MgY2FuIGJlIGluIHRoZSBzYW1lIHNxdWFyZSBhdCBhbnkgdGltZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+QWZ0ZXIgbWFueSBob3VycyBvZiBwbGF5IGFuZCB0d28gcHJldmlvdXMgYXR0ZW1wdHMsIE1pcmtvJiMzOTtzIG1vbSB5ZWxsZWQgYXQgdGhlbSB0byBjb21lIGRvd24gZm9yIGx1bmNoIGFnYWluLCBhbmQgdGhleSBkZWNpZGVkIHRvIHJlYXJyYW5nZSB0aGUgdGFua3Mgc28gdGhhdCBlYWNoIHRhbmsgZ3VhcmRzIGEgZGlmZmVyZW50IHJvdyBhbmQgY29sdW1uIChtZWFuaW5nIGFsc28gdGhhdCBlYWNoIHJvdyBhbmQgY29sdW1uIGNvbnRhaW5zIG9ubHkgb25lIHRhbmspLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ib3dldmVyLCB0aGV5IHdhbnQgdG8gZG8gdGhpcyB1c2luZyB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3ZlcyByZXF1aXJlZCB0byByZWFycmFuZ2UgdGhlIHRhbmtzIHNvIHRoYXQgZWFjaCByb3cgYW5kIGVhY2ggY29sdW1uIGNvbnRhaW5zIGEgc2luZ2xlIHRhbmssIGFuZCBvbmUgc3VjaCBzaG9ydGVzdCBzZXF1ZW5jZSBvZiBtb3Zlcy4mbmJzcDs8XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlRoZSBmaXJzdCBsaW5lIG9mIGlucHV0IGNvbnRhaW5zIHRoZSBpbnRlZ2VyIE4gKDUgJmxlOyBOICZsZTsgNTAwKS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgZm9sbG93aW5nIE4gbGluZXMgY29udGFpbnMgdHdvIGludGVnZXJzIFIgYW5kIEMgKDEgJmxlOyBSLCBTICZsZTsgTiksIHRoZSByb3cgYW5kIGNvbHVtbiBvZiBhIHNpbmdsZSB0YW5rIGF0IHRoZSBtb21lbnQgb2YgbW9tJiMzOTtzIGNhbGwuIE5vIHR3byB0YW5rcyBhcmUgb24gdGhlIHNhbWUgc3F1YXJlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Sb3dzIGFuZCBjb2x1bW5zIGFyZSBtYXJrZWQgMSB0aHJvdWdoIE4sIHRvcC1kb3duIGFuZCBsZWZ0LXRvLXJpZ2h0LiZuYnNwOzxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPk91dHB1dCB0aGUgbWluaW11bSBudW1iZXIgb2YgbW92ZXMgKGNhbGwgdGhpcyBudW1iZXIgSykgb24gdGhlIGZpcnN0IGxpbmUuJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgSyBsaW5lcyBzaG91bGQgY29udGFpbiB0aGUgdGFuayBiZWluZyBtb3ZlZCBhbmQgdGhlIGRpcmVjdGlvbiBpdCBpcyBtb3ZlZCBpbiwgc2VwYXJhdGVkIGJ5IGEgc2luZ2xlIHNwYWNlLiZuYnNwOzxcL3A+XHJcblxyXG48cD5UYW5rcyBhcmUgbnVtYmVyZWQgMSB0aHJvdWdoIE4sIGluIHRoZSBvcmRlciBpbiB3aGljaCB0aGV5IGFyZSBnaXZlbiBpbiB0aGUgaW5wdXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlRoZSBkaXJlY3Rpb24gY2FuIGJlIG9uZSBvZiBmb3VyIHVwcGVyY2FzZSBsZXR0ZXJzOiAmIzM5O0wmIzM5OyBmb3IgbGVmdCwgJiMzOTtSJiMzOTsgZm9yIHJpZ2h0LCAmIzM5O1UmIzM5OyBmb3IgdXAgYW5kICYjMzk7RCYjMzk7IGZvciBkb3duLiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgc2VxdWVuY2UgbmVlZCBub3QgYmUgdW5pcXVlLiZuYnNwOzxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==