시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 167 32 21 31.343%

문제

창영이는 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+XHJcblxyXG48cD5cclxuXHRcdWMwYzFcdWFkZmNcdWM3NzRcdWFjMDAgXHVjNzg1XHViODI1XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc3NCBcdWJhYThcdWI0NTAgXHVjOGZjXHVjNWI0XHVjODRjXHVjNzQ0IFx1YjU0YywgXHVjYzk4XHVjNzRjIFx1YzBjMVx1ZDBkY1x1Yjg1YyBcdWI5Y2NcdWI0ZTRcdWFlMzAgXHVjNzA0XHVkNTc0IFx1YjlhY1x1YzJhNFx1ZDJiOFx1YWMwMCBcdWMyMThcdWQ1ODlcdWQ1NzRcdWM1N2MgXHVkNTU4XHViMjk0IFx1YzVmMFx1YzBiMFx1Yzc0NCBcdWFkNmNcdWQ1NThcdWIyOTQgXHVkNTA0XHViODVjXHVhZGY4XHViN2E4XHVjNzQ0IFx1Yzc5MVx1YzEzMVx1ZDU1OFx1YzJkY1x1YzYyNC4gXHVjNzc0XHViNTRjLCBcdWM1ZjBcdWMwYjBcdWM3NDQgXHViNDE4XHViM2M0XHViODVkIFx1YzgwMVx1YWM4YyBcdWMwYWNcdWM2YTlcdWQ1NzRcdWM1N2MgXHVkNTVjXHViMmU0LjxcL3A+XHJcbiIsImlucHV0IjoiXHJcbjxwPlxyXG5cdFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDAgXHViMTc4XHViNGRjXHVjNzU4IFx1YzIxOCBOXHVhY2ZjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWMyMTggTVx1Yzc3NCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuICgyICZsZTsgTiAmbGU7IDUwMCwwMDAsIDAgJmxlOyBNICZsZTsgMTAwLDAwMCk8XC9wPlxyXG5cclxuPHA+XHJcblx0XHViMmU0XHVjNzRjIE1cdWFjMWMgXHVjOTA0XHVjNWQwXHViMjk0IFx1YzBjMVx1YWRmY1x1Yzc3NFx1YWMwMCBcdWM3ODVcdWI4MjVcdWQ1NWMgXHVjNWYwXHVjMGIwXHVjNzc0IFx1YmIzOFx1YzgxYyBcdWMxMjRcdWJhODVcdWM1ZDAgXHViMDk4XHVjNjI4IFx1ZDYxNVx1YzJkZFx1YzczY1x1Yjg1YyBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHJcblx0XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWNjOThcdWM3NGMgXHVjMGMxXHVkMGRjXHViODVjIFx1YjljY1x1YjRlNFx1YWUzMCBcdWM3MDRcdWQ1NzRcdWMxMWMgXHVkNTQ0XHVjNjk0XHVkNTVjIFx1YzVmMFx1YzBiMFx1Yzc1OCBcdWNkNWNcdWMxOWZcdWFjMTJcdWM3NDQgXHVjZDljXHViODI1XHVkNTVjXHViMmU0LiBcdWM3NzQgXHVhYzEyXHVjNzQ0IEtcdWI3N2NcdWFjZTAgXHVkNTVjXHViMmU0LjxcL3A+XHJcblxyXG48cD5cclxuXHRcdWIyZTRcdWM3NGMgS1x1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWFjXHVjMmE0XHVkMmI4XHVhYzAwIFx1YzIxOFx1ZDU4OVx1ZDU3NFx1YzU3YyBcdWQ1NThcdWIyOTQgXHVjNWYwXHVjMGIwXHVjNzQ0IFx1YzIxY1x1YzExY1x1YjMwMFx1Yjg1YyBcdWNkOWNcdWI4MjVcdWQ1NWNcdWIyZTQuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMCIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVkNTVjXHVhZDZkXHVjNWI0In0seyJwcm9ibGVtX2lkIjoiMzA0NSIsInByb2JsZW1fbGFuZyI6IjEiLCJ0aXRsZSI6IkxJU1RBIiwiZGVzY3JpcHRpb24iOiI8cD5NaXJrbyByZWNlaXZlZCBhIGJpcnRoZGF5IHByZXNlbnQgZnJvbSBoaXMgYXVudCBpbiB0aGUgVVMgJm5kYXNoOyBhIGJyYW5kLW5ldyBkb3VibHktbGlua2VkIGxpc3QgKGFuIGV4YW1wbGUgb2Ygd2hpY2ggaXMgc2hvd24gaW4gdGhlIGZpZ3VyZSBiZWxvdykuIFRoZSBsaXN0IGNvbnRhaW5zIE4gbm9kZXMgbnVtYmVyZWQgMSB0aHJvdWdoIE4uIFR3byB0eXBlcyBvZiBtb3ZlcyBjYW4gYmUgZG9uZSBvbiB0aGUgbGlzdDombmJzcDs8XC9wPlxyXG5cclxuPHA+QSkgTW92ZSBub2RlIFggaW4gZnJvbnQgb2Ygbm9kZSBZLiZuYnNwOzxiciBcLz5cclxuQikgTW92ZSBub2RlIFggYWZ0ZXIgbm9kZSBZLiZuYnNwOzxcL3A+XHJcblxyXG48cD48aW1nIGFsdD1cIlwiIHNyYz1cIlwvdXBsb2FkXC9pbWFnZXNcL2xpc3QxLnBuZ1wiIHN0eWxlPVwiaGVpZ2h0Ojc4cHg7IHdpZHRoOjUzN3B4XCIgXC8+PFwvcD5cclxuXHJcbjxwPkFuIGV4YW1wbGUgb2YgYSBsaXN0IHdpdGggNiBub2Rlcy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9saXN0Mi5wbmdcIiBzdHlsZT1cImhlaWdodDo3OHB4OyB3aWR0aDo1MzdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbGlzdCBhZnRlciB0aGUgbW92ZSAmcXVvdDtBIDEgNCZxdW90Oy4mbmJzcDs8XC9wPlxyXG5cclxuPHA+PGltZyBhbHQ9XCJcIiBzcmM9XCJcL3VwbG9hZFwvaW1hZ2VzXC9saXN0My5wbmdcIiBzdHlsZT1cImhlaWdodDo3OHB4OyB3aWR0aDo1MzdweFwiIFwvPjxcL3A+XHJcblxyXG48cD5UaGUgbGlzdCBhZnRlciBhbm90aGVyIG1vdmUsICZxdW90O0IgMyA1JnF1b3Q7LiZuYnNwOzxcL3A+XHJcblxyXG48cD5NaXJrbyBwbGF5ZWQgd2l0aCBoaXMgbmV3IHRveSBmb3IgaG91cnMsIHdyaXRpbmcgZG93biBlYWNoIG1vdmUgb24gYSBwaWVjZSBvZiBwYXBlciBzbyB0aGF0IGhlIGNhbiByZWNvbnN0cnVjdCB0aGUgbGlzdCYjMzk7cyBpbml0aWFsIHN0YXRlIChub2RlcyAxIHRocm91Z2ggTiBpbiBvcmRlciBmcm9tIGxlZnQgdG8gcmlnaHQpLiZuYnNwOzxcL3A+XHJcblxyXG48cD5XaGVuIGhlIGRlY2lkZWQgdG8gcmVjb25zdHJ1Y3QgdGhlIGxpc3QsIE1pcmtvIHdhcyBhc3RvbmlzaGVkIHRvIGZpbmQgdGhhdCB0aGVyZSBpcyBubyBlYXN5IHdheSB0byBpbnZlcnQgdGhlIG1vdmVzIGFuZCByZXN0b3JlIHRoZSBsaXN0JiMzOTtzIGluaXRpYWwgc3RhdGUuIE1pcmtvIGNhbm5vdCBrbm93IHdoZXJlIG5vZGUgWCB3YXMgcHJpb3IgdG8gZWFjaCBtb3ZlLCBvbmx5IHdoZXJlIGl0IGVuZGVkIHVwLiZuYnNwOzxcL3A+XHJcblxyXG48cD5TZWVpbmcgaG93IE1pcmtvIGlzIHN0aWxsIHJlY292ZXJpbmcgZnJvbSB0aGUgc2hvY2ssIHdyaXRlIGEgcHJvZ3JhbSB0aGF0IGZpbmRzIGEgbWluaW1hbCBzZXF1ZW5jZSBvZiBtb3ZlcyB0aGF0IHJlc3RvcmVkIHRoZSBsaXN0JiMzOTtzIGluaXRpYWwgc3RhdGUgZnJvbSBNaXJrbyYjMzk7cyBsb2dzLjxcL3A+XHJcblxyXG48cD4mbmJzcDs8XC9wPlxyXG5cclxuPHA+Jm5ic3A7PFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyB0d28gaW50ZWdlcnMgTiBhbmQgSyAoMiAmbGU7IE4gJmxlOyA1MDAgMDAwLCAwICZsZTsgTSAmbGU7IDEwMCAwMDApLCB0aGUgbnVtYmVyIG9mIG5vZGVzIGFuZCB0aGUgbnVtYmVyIG9mIG1vdmVzIG1hZGUgYnkgTWlya28uJm5ic3A7PFwvcD5cclxuXHJcbjxwPkVhY2ggb2YgdGhlIG5leHQgTSByb3dzIGNvbnRhaW5zIGEgZGVzY3JpcHRpb24gb2YgYSBzaW5nbGUgbW92ZSBtYWRlIGJ5IE1pcmtvICZuZGFzaDsgdGhlIHR5cGUgb2YgbW92ZSAoJiMzOTtBJiMzOTsgb3IgJiMzOTtCJiMzOTspIGFuZCB0d28gaW50ZWdlcnMgWCBhbmQgWS4mbmJzcDs8XC9wPlxyXG4iLCJvdXRwdXQiOiI8cD5PdXRwdXQgdGhlIG1pbmltdW0gbnVtYmVyIG9mIG1vdmVzIChjYWxsIHRoaXMgbnVtYmVyIEspIG9uIHRoZSBmaXJzdCBsaW5lLiZuYnNwOzxcL3A+XHJcblxyXG48cD5FYWNoIG9mIHRoZSBuZXh0IEsgbGluZXMgc2hvdWxkIGNvbnRhaW4gYSBkZXNjcmlwdGlvbiBvZiBhIHNpbmdsZSBtb3ZlIGluIHRoZSBzYW1lIGZvcm1hdCBhcyBpbiB0aGUgaW5wdXQuJm5ic3A7PFwvcD5cclxuXHJcbjxwPk5vdGU6IFRoZSBzZXF1ZW5jZSBuZWVkIG5vdCBiZSB1bmlxdWUuPFwvcD5cclxuIiwiaGludCI6IiIsIm9yaWdpbmFsIjoiMSIsInByb2JsZW1fbGFuZ19jb2RlIjoiXHVjNjAxXHVjNWI0In1d