시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 111 20 15 31.915%

문제

창영이는 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
W3sicHJvYmxlbV9pZCI6IjMwNDUiLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWM3NzRcdWM5MTEgXHVjNWYwXHVhY2IwIFx1YjlhY1x1YzJhNFx1ZDJiOCIsImRlc2NyaXB0aW9uIjoiPHA+XHJcblx0XHVjYzNkXHVjNjAxXHVjNzc0XHViMjk0IDFcdWQ1NTlcdWIxNDQgXHViNTRjIFx1YzIxOVx1YzgxY1x1Yjg1YyBcdWQ1ODhcdWIzNTggXHVjNzc0XHVjOTExIFx1YzVmMFx1YWNiMCBcdWI5YWNcdWMyYTRcdWQyYjggXHVjMThjXHVjMmE0XHViOTdjIFx1YzBjMVx1YWRmY1x1Yzc3NFx1YzVkMFx1YWM4YyBcdWMwZGRcdWM3N2MgXHVjMTIwXHViYjNjXHViODVjIFx1YmNmNFx1YjBiNFx1YzhmY1x1YzVjOFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1YjRkY1x1YjUxNFx1YzViNCBcdWM3OTBcdWMyZTBcdWM3NzQgXHVjNmQwXHVkNTU4XHViMzU4IFx1YWUzMFx1YjJhNVx1Yzc3NCBcdWM3ODhcdWIyOTQgXHVjMThjXHVjMmE0XHViOTdjIFx1YmMxYlx1YWM4YyBcdWI0MThcdWM1YjRcdWMxMWMgXHViOWU0XHVjNmIwIFx1YWUzMFx1YmVlNFx1YjJlNC4gXHVjMGMxXHVhZGZjXHVjNzc0XHViMjk0IFx1ZDU1OFx1YjhlOFx1Yzg4NVx1Yzc3YyBcdWM3NzQgXHViOWFjXHVjMmE0XHVkMmI4XHViOTdjIFx1YWMwMFx1YzljMFx1YWNlMCBcdWIxODBcdWI4MjRcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWI5YWNcdWMyYTRcdWQyYjhcdWM1ZDBcdWIyOTQgXHVjZDFkIE5cdWFjMWNcdWM3NTggXHViMTc4XHViNGRjXHVhYzAwIFx1ZDNlY1x1ZDU2OFx1YjQxOFx1YzViNCBcdWM3ODhcdWFjZTAsIFx1YWMwMFx1YzdhNSBcdWM2N2NcdWNhYmQgXHViMTc4XHViNGRjXHVhYzAwIDFcdWJjODhcdWM3NzRcdWJhNzAgXHViMDk4XHViYTM4XHVjOWMwXHViMjk0IFx1YzYyNFx1Yjk3OFx1Y2FiZFx1YzczY1x1Yjg1YyBcdWFjMDggXHVjMjE4XHViODVkIDFcdWM1MjkgXHViYzg4XHVkNjM4XHVhYzAwIFx1Yzk5ZFx1YWMwMFx1ZDU1Y1x1YjJlNC4gXHViOWFjXHVjMmE0XHVkMmI4XHVhYzAwIFx1YzIxOFx1ZDU4OVx1ZDU2MCBcdWMyMTggXHVjNzg4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0MCBcdWM1NDRcdWI3OThcdWM2NDAgXHVhYzE5XHVjNzc0IDJcdWFjMDBcdWM5YzBcdWM3NzRcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlxyXG5cdEEpIFx1YjE3OFx1YjRkYyBYXHViOTdjIFx1YjE3OFx1YjRkYyBZXHVjNzU4IFx1YzU1ZVx1YzczY1x1Yjg1YyBcdWM3NzRcdWIzZDk8XC9wPlxyXG48cD5cclxuXHRCKSBcdWIxNzhcdWI0ZGMgWFx1Yjk3YyBcdWIxNzhcdWI0ZGMgWVx1Yzc1OCBcdWI0YTRcdWM3M2NcdWI4NWMgXHVjNzc0XHViM2Q5PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWM3NDAgXHViMTc4XHViNGRjXHVhYzAwIDZcdWFjMWNcdWM3NzggXHVjNzc0XHVjOTExIFx1YzVmMFx1YWNiMCBcdWI5YWNcdWMyYTRcdWQyYjhcdWM3NTggXHViYWE4XHVjMmI1XHVjNzc0XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xpc3QxLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDUzN3B4OyBoZWlnaHQ6IDc4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YzVlY1x1YWUzMFx1YzVkMCAmcXVvdDtBIDEgNCZxdW90OyBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHViYTc0IFx1YzU0NFx1Yjc5OFx1YzY0MCBcdWFjMTlcdWM3NzQgXHViNDFjXHViMmU0LiAoXHViMTc4XHViNGRjIDFcdWM3NDQgXHViMTc4XHViNGRjIDRcdWM3NTggXHVjNTVlXHVjNzNjXHViODVjIFx1Yzc3NFx1YjNkOSk8XC9wPlxyXG5cclxuPHA+XHJcblx0PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9saXN0Mi5wbmdcIiBzdHlsZT1cIndpZHRoOiA1MzdweDsgaGVpZ2h0OiA3OHB4O1wiIFwvPjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWFkZjggXHViMmU0XHVjNzRjLCAmcXVvdDtCIDMgNSZxdW90OyBcdWM1ZjBcdWMwYjBcdWM3NDQgXHVjMjE4XHVkNTg5XHVkNTU4XHViYTc0IFx1YzU0NFx1Yjc5OCBcdWFkZjhcdWI5YmNcdWFjZmMgXHVhYzE5XHVjNzQwIFx1YmFhOFx1YzJiNVx1Yzc3NCBcdWI0MWNcdWIyZTQuIChcdWIxNzhcdWI0ZGMgM1x1Yzc0NCBcdWIxNzhcdWI0ZGMgNVx1Yzc1OCBcdWI0YTRcdWI4NWMgXHVjNzc0XHViM2Q5KTxcL3A+XHJcblxyXG48cD5cclxuXHQ8aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xpc3QzLnBuZ1wiIHN0eWxlPVwid2lkdGg6IDUzN3B4OyBoZWlnaHQ6IDc4cHg7XCIgXC8+PFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjlhY1x1YzJhNFx1ZDJiOFx1Yjk3YyBcdWFjMDBcdWM5YzBcdWFjZTAgXHViMmU0IFx1YjE3YyBcdWIyZTRcdWM3NGNcdWM1ZDBcdWIyOTQgXHVjYzk4XHVjNzRjIFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWIyZTRcdWMyZGMgXHViOWNjXHViNGU0XHVjNWI0XHVjNTdjIFx1ZDU1Y1x1YjJlNC4gXHViNTMwXHViNzdjXHVjMTFjLCBcdWMwYzFcdWFkZmNcdWM3NzRcdWIyOTQgXHViOWFjXHVjMmE0XHVkMmI4XHVjNWQwIFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWM3ODVcdWI4MjVcdWQ1NjAgXHViNTRjIFx1YjljOFx1YjJlNCBcdWM4ODVcdWM3NzRcdWM1ZDAgXHVjODAxXHVjNWI0XHViNDUwXHVjNWM4XHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjYzk4XHVjNzRjIFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YWMwMCBcdWMyMThcdWQ1ODlcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNzc0IFx1YjU0YywgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YjQxOFx1YjNjNFx1Yjg1ZCBcdWM4MDFcdWFjOGMgXHVjMGFjXHVjNmE5XHVkNTc0XHVjNTdjIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG4iLCJpbnB1dCI6IlxyXG48cD5cclxuXHRcdWNjYWJcdWM5ZjggXHVjOTA0XHVjNWQwIFx1YjE3OFx1YjRkY1x1Yzc1OCBcdWMyMTggTlx1YWNmYyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjMjE4IE1cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiAoMiAmbGU7IE4gJmxlOyA1MDAsMDAwLCAwICZsZTsgTSAmbGU7IDEwMCwwMDApPFwvcD5cclxuXHJcbjxwPlxyXG5cdFx1YjJlNFx1Yzc0YyBNXHVhYzFjIFx1YzkwNFx1YzVkMFx1YjI5NCBcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWJiMzhcdWM4MWMgXHVjMTI0XHViYTg1XHVjNWQwIFx1YjA5OFx1YzYyOCBcdWQ2MTVcdWMyZGRcdWM3M2NcdWI4NWMgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LjxcL3A+XHJcbiIsIm91dHB1dCI6IjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHVjYzk4XHVjNzRjIFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0XHVjMTFjIFx1ZDU0NFx1YzY5NFx1ZDU1YyBcdWM1ZjBcdWMwYjBcdWM3NTggXHVjZDVjXHVjMThjXHVhYzEyXHVjNzQ0IFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjNzc0IFx1YWMxMlx1Yzc0NCBLXHViNzdjXHVhY2UwIFx1ZDU1Y1x1YjJlNC48XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIEtcdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YWMwMCBcdWMyMThcdWQ1ODlcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWMyMWNcdWMxMWNcdWIzMDBcdWI4NWMgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjAiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1ZDU1Y1x1YWQ2ZFx1YzViNCJ9LHsicHJvYmxlbV9pZCI6IjMwNDUiLCJwcm9ibGVtX2xhbmciOiIxIiwidGl0bGUiOiJMSVNUQSIsImRlc2NyaXB0aW9uIjoiPHA+TWlya28gcmVjZWl2ZWQgYSBiaXJ0aGRheSBwcmVzZW50IGZyb20gaGlzIGF1bnQgaW4gdGhlIFVTICZuZGFzaDsgYSBicmFuZC1uZXcgZG91Ymx5LWxpbmtlZCBsaXN0IChhbiBleGFtcGxlIG9mIHdoaWNoIGlzIHNob3duIGluIHRoZSBmaWd1cmUgYmVsb3cpLiBUaGUgbGlzdCBjb250YWlucyBOIG5vZGVzIG51bWJlcmVkIDEgdGhyb3VnaCBOLiBUd28gdHlwZXMgb2YgbW92ZXMgY2FuIGJlIGRvbmUgb24gdGhlIGxpc3Q6Jm5ic3A7PFwvcD5cclxuXHJcbjxwPkEpIE1vdmUgbm9kZSBYIGluIGZyb250IG9mIG5vZGUgWS4mbmJzcDs8YnIgXC8+XHJcbkIpIE1vdmUgbm9kZSBYIGFmdGVyIG5vZGUgWS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9saXN0MS5wbmdcIiBzdHlsZT1cImhlaWdodDo3OHB4OyB3aWR0aDo1MzdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5BbiBleGFtcGxlIG9mIGEgbGlzdCB3aXRoIDYgbm9kZXMuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbGlzdDIucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzhweDsgd2lkdGg6NTM3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGxpc3QgYWZ0ZXIgdGhlIG1vdmUgJnF1b3Q7QSAxIDQmcXVvdDsuJm5ic3A7PFwvcD5cclxuXHJcbjxwPjxpbWcgYWx0PVwiXCIgc3JjPVwiXC91cGxvYWRcL2ltYWdlc1wvbGlzdDMucG5nXCIgc3R5bGU9XCJoZWlnaHQ6NzhweDsgd2lkdGg6NTM3cHhcIiBcLz48XC9wPlxyXG5cclxuPHA+VGhlIGxpc3QgYWZ0ZXIgYW5vdGhlciBtb3ZlLCAmcXVvdDtCIDMgNSZxdW90Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+TWlya28gcGxheWVkIHdpdGggaGlzIG5ldyB0b3kgZm9yIGhvdXJzLCB3cml0aW5nIGRvd24gZWFjaCBtb3ZlIG9uIGEgcGllY2Ugb2YgcGFwZXIgc28gdGhhdCBoZSBjYW4gcmVjb25zdHJ1Y3QgdGhlIGxpc3QmIzM5O3MgaW5pdGlhbCBzdGF0ZSAobm9kZXMgMSB0aHJvdWdoIE4gaW4gb3JkZXIgZnJvbSBsZWZ0IHRvIHJpZ2h0KS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+V2hlbiBoZSBkZWNpZGVkIHRvIHJlY29uc3RydWN0IHRoZSBsaXN0LCBNaXJrbyB3YXMgYXN0b25pc2hlZCB0byBmaW5kIHRoYXQgdGhlcmUgaXMgbm8gZWFzeSB3YXkgdG8gaW52ZXJ0IHRoZSBtb3ZlcyBhbmQgcmVzdG9yZSB0aGUgbGlzdCYjMzk7cyBpbml0aWFsIHN0YXRlLiBNaXJrbyBjYW5ub3Qga25vdyB3aGVyZSBub2RlIFggd2FzIHByaW9yIHRvIGVhY2ggbW92ZSwgb25seSB3aGVyZSBpdCBlbmRlZCB1cC4mbmJzcDs8XC9wPlxyXG5cclxuPHA+U2VlaW5nIGhvdyBNaXJrbyBpcyBzdGlsbCByZWNvdmVyaW5nIGZyb20gdGhlIHNob2NrLCB3cml0ZSBhIHByb2dyYW0gdGhhdCBmaW5kcyBhIG1pbmltYWwgc2VxdWVuY2Ugb2YgbW92ZXMgdGhhdCByZXN0b3JlZCB0aGUgbGlzdCYjMzk7cyBpbml0aWFsIHN0YXRlIGZyb20gTWlya28mIzM5O3MgbG9ncy48XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuXHJcbjxwPiZuYnNwOzxcL3A+XHJcbiIsImlucHV0IjoiPHA+VGhlIGZpcnN0IGxpbmUgb2YgaW5wdXQgY29udGFpbnMgdHdvIGludGVnZXJzIE4gYW5kIEsgKDIgJmxlOyBOICZsZTsgNTAwIDAwMCwgMCAmbGU7IE0gJmxlOyAxMDAgMDAwKSwgdGhlIG51bWJlciBvZiBub2RlcyBhbmQgdGhlIG51bWJlciBvZiBtb3ZlcyBtYWRlIGJ5IE1pcmtvLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IE0gcm93cyBjb250YWlucyBhIGRlc2NyaXB0aW9uIG9mIGEgc2luZ2xlIG1vdmUgbWFkZSBieSBNaXJrbyAmbmRhc2g7IHRoZSB0eXBlIG9mIG1vdmUgKCYjMzk7QSYjMzk7IG9yICYjMzk7QiYjMzk7KSBhbmQgdHdvIGludGVnZXJzIFggYW5kIFkuJm5ic3A7PFwvcD5cclxuIiwib3V0cHV0IjoiPHA+T3V0cHV0IHRoZSBtaW5pbXVtIG51bWJlciBvZiBtb3ZlcyAoY2FsbCB0aGlzIG51bWJlciBLKSBvbiB0aGUgZmlyc3QgbGluZS4mbmJzcDs8XC9wPlxyXG5cclxuPHA+RWFjaCBvZiB0aGUgbmV4dCBLIGxpbmVzIHNob3VsZCBjb250YWluIGEgZGVzY3JpcHRpb24gb2YgYSBzaW5nbGUgbW92ZSBpbiB0aGUgc2FtZSBmb3JtYXQgYXMgaW4gdGhlIGlucHV0LiZuYnNwOzxcL3A+XHJcblxyXG48cD5Ob3RlOiBUaGUgc2VxdWVuY2UgbmVlZCBub3QgYmUgdW5pcXVlLjxcL3A+XHJcbiIsImhpbnQiOiIiLCJvcmlnaW5hbCI6IjEiLCJwcm9ibGVtX2xhbmdfY29kZSI6Ilx1YzYwMVx1YzViNCJ9XQ==