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

문제

창영이는 1학년 때 숙제로 했던 이중 연결 리스트 소스를 상근이에게 생일 선물로 보내주었다. 상근이는 드디어 자신이 원하던 기능이 있는 소스를 받게 되어서 매우 기뻤다. 상근이는 하루종일 이 리스트를 가지고 놀려고 한다.

리스트에는 총 N개의 노드가 포함되어 있고, 가장 왼쪽 노드가 1번이며 나머지는 오른쪽으로 갈 수록 1씩 번호가 증가한다. 리스트가 수행할 수 있는 연산은 아래와 같이 2가지이다.

A) 노드 X를 노드 Y의 앞으로 이동

B) 노드 X를 노드 Y의 뒤으로 이동

아래 그림은 노드가 6개인 이중 연결 리스트의 모습이다.

여기에 "A 1 4" 연산을 수행하면 아래와 같이 된다. (노드 1을 노드 4의 앞으로 이동)

그 다음, "B 3 5" 연산을 수행하면 아래 그림과 같은 모습이 된다. (노드 3을 노드 5의 뒤로 이동)

리스트를 가지고 다 논 다음에는 처음 상태로 다시 만들어야 한다. 따라서, 상근이는 리스트에 연산을 입력할 때 마다 종이에 적어두었다.

상근이가 입력한 연산이 모두 주어졌을 때, 처음 상태로 만들기 위해 리스트가 수행해야 하는 연산을 구하는 프로그램을 작성하시오. 이때, 연산을 되도록 적게 사용해야 한다.

입력

첫째 줄에 노드의 수 N과 연산의 수 M이 주어진다. (2 ≤ N ≤ 500,000, 0 ≤ M ≤ 100,000)

다음 M개 줄에는 상근이가 입력한 연산이 문제 설명에 나온 형식으로 주어진다.

출력

첫째 줄에 처음 상태로 만들기 위해서 필요한 연산의 최솟값을 출력한다. 이 값을 K라고 한다.

다음 K개 줄에는 리스트가 수행해야 하는 연산을 순서대로 출력한다.

예제 입력 1

2 1
A 2 1

예제 출력 1

1
A 1 2

예제 입력 2

4 3
B 1 2
A 4 3
B 1 4

예제 출력 2

2
A 1 2
B 4 3

예제 입력 3

6 5
A 1 4
B 2 5
B 4 2
B 6 3
A 3 5

예제 출력 3

3
A 4 5
B 6 5
A 2 3
W3sicHJvYmxlbV9pZCI6IjMwNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5MTEgXHVjNWYwXHVhY2IwIFx1YjlhY1x1YzJhNFx1ZDJiOCIsImRlc2NyaXB0aW9uIjoiPHA+XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IDFcdWQ1NTlcdWIxNDQgXHViNTRjIFx1YzIxOVx1YzgxY1x1Yjg1YyBcdWQ1ODhcdWIzNTggXHVjNzc0XHVjOTExIFx1YzVmMFx1YWNiMCBcdWI5YWNcdWMyYTRcdWQyYjggXHVjMThjXHVjMmE0XHViOTdjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWMwZGRcdWM3N2MgXHVjMTIwXHViYjNjXHViODVjIFx1YmNmNFx1YjBiNFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjRkY1x1YjUxNFx1YzViNCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNmQwXHVkNTU4XHViMzU4IFx1YWUzMFx1YjJhNVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjMmE0XHViOTdjIFx1YmMxYlx1YWM4YyBcdWI0MThcdWM1YjRcdWMxMWMgXHViOWU0XHVjNmIwIFx1YWUzMFx1YmVlNFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDU1OFx1YjhlOFx1Yzg4NVx1Yzc3YyBcdWM3NzQgXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWIxODBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDBcdWIyOTQgXHVjZDFkIE5cdWFjMWNcdWM3NTggXHViMTc4XHViNGRjXHVhYzAwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHViMTc4XHViNGRjXHVhYzAwIDFcdWJjODhcdWM3NzRcdWJhNzAgXHViMDk4XHViYTM4XHVjOWMwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4XHViODVkIDFcdWM1MjkgXHViYzg4XHVkNjM4XHVhYzAwIFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNC4gXHViOWFjXHVjMmE0XHVkMmI4XHVhYzAwIFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDJcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPkEpIFx1YjE3OFx1YjRkYyBYXHViOTdjIFx1YjE3OFx1YjRkYyBZXHVjNzU4IFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDk8XC9wPlxyXG5cclxuPHA+QikgXHViMTc4XHViNGRjIFhcdWI5N2MgXHViMTc4XHViNGRjIFlcdWM3NTggXHViNGE0XHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOTxcL3A+XHJcblxyXG48cD5cdWM1NDRcdWI3OTggXHVhZGY4XHViOWJjXHVjNzQwIFx1YjE3OFx1YjRkY1x1YWMwMCA2XHVhYzFjXHVjNzc4IFx1Yzc3NFx1YzkxMSBcdWM1ZjBcdWFjYjAgXHViOWFjXHVjMmE0XHVkMmI4XHVjNzU4IFx1YmFhOFx1YzJiNVx1Yzc3NFx1YjJlNC48XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC81YjM0OTA1Yy01NjdmLTQ4M2QtODYwYS1iODA2NjdmMGM3ZjlcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDUxOHB4OyBoZWlnaHQ6IDU1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YzVlY1x1YWUzMFx1YzVkMCAmcXVvdDtBIDEgNCZxdW90OyBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViNDFjXHViMmU0LiAoXHViMTc4XHViNGRjIDFcdWM3NDQgXHViMTc4XHViNGRjIDRcdWM3NTggXHVjNTVlXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOSk8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC83NjA5YmYyNi1kMzgyLTRjODktOGMwMy1hZjg1MjQ2NTQ4YmNcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDUxOHB4OyBoZWlnaHQ6IDU0cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlx1YWRmOCBcdWIyZTRcdWM3NGMsICZxdW90O0IgMyA1JnF1b3Q7IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWMyMThcdWQ1ODlcdWQ1NThcdWJhNzQgXHVjNTQ0XHViNzk4IFx1YWRmOFx1YjliY1x1YWNmYyBcdWFjMTlcdWM3NDAgXHViYWE4XHVjMmI1XHVjNzc0IFx1YjQxY1x1YjJlNC4gKFx1YjE3OFx1YjRkYyAzXHVjNzQ0IFx1YjE3OFx1YjRkYyA1XHVjNzU4IFx1YjRhNFx1Yjg1YyBcdWM3NzRcdWIzZDkpPFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvMzU4MDM3MTctOWQzNy00YTk4LTljMTctZTU1Mzg5MTRhMTM0XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1MThweDsgaGVpZ2h0OiA1NXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cdWI5YWNcdWMyYTRcdWQyYjhcdWI5N2MgXHVhYzAwXHVjOWMwXHVhY2UwIFx1YjJlNCBcdWIxN2MgXHViMmU0XHVjNzRjXHVjNWQwXHViMjk0IFx1Y2M5OFx1Yzc0YyBcdWMwYzFcdWQwZGNcdWI4NWMgXHViMmU0XHVjMmRjIFx1YjljY1x1YjRlNFx1YzViNFx1YzU3YyBcdWQ1NWNcdWIyZTQuIFx1YjUzMFx1Yjc3Y1x1YzExYywgXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YzVkMCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjNzg1XHViODI1XHVkNTYwIFx1YjU0YyBcdWI5YzhcdWIyZTQgXHVjODg1XHVjNzc0XHVjNWQwIFx1YzgwMVx1YzViNFx1YjQ1MFx1YzVjOFx1YjJlNC48XC9wPlxyXG5cclxuPHA+XHVjMGMxXHVhZGZjXHVjNzc0XHVhYzAwIFx1Yzc4NVx1YjgyNVx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NzQgXHViYWE4XHViNDUwIFx1YzhmY1x1YzViNFx1Yzg0Y1x1Yzc0NCBcdWI1NGMsIFx1Y2M5OFx1Yzc0YyBcdWMwYzFcdWQwZGNcdWI4NWMgXHViOWNjXHViNGU0XHVhZTMwIFx1YzcwNFx1ZDU3NCBcdWI5YWNcdWMyYTRcdWQyYjhcdWFjMDAgXHVjMjE4XHVkNTg5XHVkNTc0XHVjNTdjIFx1ZDU1OFx1YjI5NCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVhZDZjXHVkNTU4XHViMjk0IFx1ZDUwNFx1Yjg1Y1x1YWRmOFx1YjdhOFx1Yzc0NCBcdWM3OTFcdWMxMzFcdWQ1NThcdWMyZGNcdWM2MjQuIFx1Yzc3NFx1YjU0YywgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM4MDFcdWFjOGMgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IjxwPlx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDUwMCwwMDAsIDAgJmxlOyBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzc0IFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM1ZDAgXHViMDk4XHVjNjI4IFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjOThcdWM3NGMgXHVjMGMxXHVkMGRjXHViODVjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQ0IEtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cdWIyZTRcdWM3NGMgS1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWFjXHVjMmE0XHVkMmI4XHVhYzAwIFx1YzIxOFx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiS29yZWFuIn0seyJwcm9ibGVtX2lkIjoiMzA0NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxJU1RBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyByZWNlaXZlZCBhIGJpcnRoZGF5IHByZXNlbnQgZnJvbSBoaXMgYXVudCBpbiB0aGUgVVMgJm5kYXNoOyBhIGJyYW5kLW5ldyBkb3VibHktbGlua2VkIGxpc3QgKGFuIGV4YW1wbGUgb2Ygd2hpY2ggaXMgc2hvd24gaW4gdGhlIGZpZ3VyZSBiZWxvdykuIFRoZSBsaXN0IGNvbnRhaW5zIE4gbm9kZXMgbnVtYmVyZWQgMSB0aHJvdWdoIE4uIFR3byB0eXBlcyBvZiBtb3ZlcyBjYW4gYmUgZG9uZSBvbiB0aGUgbGlzdDombmJzcDs8XC9wPlxyXG5cclxuPHA+QSkgTW92ZSBub2RlIFggaW4gZnJvbnQgb2Ygbm9kZSBZLiZuYnNwOzxcL3A+XHJcblxyXG48cD5CKSBNb3ZlIG5vZGUgWCBhZnRlciBub2RlIFkuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNWIzNDkwNWMtNTY3Zi00ODNkLTg2MGEtYjgwNjY3ZjBjN2Y5XC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1MThweDsgaGVpZ2h0OiA1NXB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5BbiBleGFtcGxlIG9mIGEgbGlzdCB3aXRoIDYgbm9kZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPjxpbWcgYWx0PVwiXCIgc3JjPVwiaHR0cHM6XC9cL3VwbG9hZC5hY21pY3BjLm5ldFwvNzYwOWJmMjYtZDM4Mi00Yzg5LThjMDMtYWY4NTI0NjU0OGJjXC8tXC9wcmV2aWV3XC9cIiBzdHlsZT1cIndpZHRoOiA1MThweDsgaGVpZ2h0OiA1NHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cCBzdHlsZT1cInRleHQtYWxpZ246IGNlbnRlcjtcIj5UaGUgbGlzdCBhZnRlciB0aGUgbW92ZSAmcXVvdDtBIDEgNCZxdW90Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHAgc3R5bGU9XCJ0ZXh0LWFsaWduOiBjZW50ZXI7XCI+PGltZyBhbHQ9XCJcIiBzcmM9XCJodHRwczpcL1wvdXBsb2FkLmFjbWljcGMubmV0XC8zNTgwMzcxNy05ZDM3LTRhOTgtOWMxNy1lNTUzODkxNGExMzRcLy1cL3ByZXZpZXdcL1wiIHN0eWxlPVwid2lkdGg6IDUxOHB4OyBoZWlnaHQ6IDU1cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwIHN0eWxlPVwidGV4dC1hbGlnbjogY2VudGVyO1wiPlRoZSBsaXN0IGFmdGVyIGFub3RoZXIgbW92ZSwgJnF1b3Q7QiAzIDUmcXVvdDsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk1pcmtvIHBsYXllZCB3aXRoIGhpcyBuZXcgdG95IGZvciBob3Vycywgd3JpdGluZyBkb3duIGVhY2ggbW92ZSBvbiBhIHBpZWNlIG9mIHBhcGVyIHNvIHRoYXQgaGUgY2FuIHJlY29uc3RydWN0IHRoZSBsaXN0JiMzOTtzIGluaXRpYWwgc3RhdGUgKG5vZGVzIDEgdGhyb3VnaCBOIGluIG9yZGVyIGZyb20gbGVmdCB0byByaWdodCkuJm5ic3A7PFwvcD5cclxuXHJcbjxwPldoZW4gaGUgZGVjaWRlZCB0byByZWNvbnN0cnVjdCB0aGUgbGlzdCwgTWlya28gd2FzIGFzdG9uaXNoZWQgdG8gZmluZCB0aGF0IHRoZXJlIGlzIG5vIGVhc3kgd2F5IHRvIGludmVydCB0aGUgbW92ZXMgYW5kIHJlc3RvcmUgdGhlIGxpc3QmIzM5O3MgaW5pdGlhbCBzdGF0ZS4gTWlya28gY2Fubm90IGtub3cgd2hlcmUgbm9kZSBYIHdhcyBwcmlvciB0byBlYWNoIG1vdmUsIG9ubHkgd2hlcmUgaXQgZW5kZWQgdXAuJm5ic3A7PFwvcD5cclxuXHJcbjxwPlNlZWluZyBob3cgTWlya28gaXMgc3RpbGwgcmVjb3ZlcmluZyBmcm9tIHRoZSBzaG9jaywgd3JpdGUgYSBwcm9ncmFtIHRoYXQgZmluZHMgYSBtaW5pbWFsIHNlcXVlbmNlIG9mIG1vdmVzIHRoYXQgcmVzdG9yZWQgdGhlIGxpc3QmIzM5O3MgaW5pdGlhbCBzdGF0ZSBmcm9tIE1pcmtvJiMzOTtzIGxvZ3MuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgSyAoMiAmbGU7IE4gJmxlOyA1MDAgMDAwLCAwICZsZTsgTSAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIG5vZGVzIGFuZCB0aGUgbnVtYmVyIG9mIG1vdmVzIG1hZGUgYnkgTWlya28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTSByb3dzIGNvbnRhaW5zIGEgZGVzY3JpcHRpb24gb2YgYSBzaW5nbGUgbW92ZSBtYWRlIGJ5IE1pcmtvICZuZGFzaDsgdGhlIHR5cGUgb2YgbW92ZSAoJiMzOTtBJiMzOTsgb3IgJiMzOTtCJiMzOTspIGFuZCB0d28gaW50ZWdlcnMgWCBhbmQgWS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIChjYWxsIHRoaXMgbnVtYmVyIEspIG9uIHRoZSBmaXJzdCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IEsgbGluZXMgc2hvdWxkIGNvbnRhaW4gYSBkZXNjcmlwdGlvbiBvZiBhIHNpbmdsZSBtb3ZlIGluIHRoZSBzYW1lIGZvcm1hdCBhcyBpbiB0aGUgaW5wdXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSBzZXF1ZW5jZSBuZWVkIG5vdCBiZSB1bmlxdWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsImh0bWxfdGl0bGUiOiIwIiwicHJvYmxlbV9sYW5nX3Rjb2RlIjoiRW5nbGlzaCJ9XQ==

출처

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