Lista

Mirko는 미국에 있는 이모에게서 생일 선물을 받았다. 바로 새 이중 연결 리스트(아래 그림에 예시가 있다)이다. 리스트에는 \(1\)부터 \(N\)까지 번호가 붙은 \(N\)개의 노드가 있다. 리스트에는 두 종류의 이동을 할 수 있다:

A) 노드 \(X\)를 노드 \(Y\) 앞으로 옮긴다.
B) 노드 \(X\)를 노드 \(Y\) 뒤로 옮긴다.

\(N\)개의 노드로 이루어진 리스트의 예.

이동 A 1 4 이후의 리스트.

또 한 번의 이동 B 3 5 이후의 리스트.

Mirko는 몇 시간이고 새 장난감을 가지고 놀았고, 리스트의 초기 상태(노드 \(1\)부터 \(N\)까지 왼쪽에서 오른쪽 순서)를 복원할 수 있도록 각 이동을 종이에 적어 두었다.

리스트를 복원하려고 했을 때, Mirko는 이동을 거꾸로 되돌려 초기 상태를 복원할 쉬운 방법이 없다는 사실에 크게 놀랐다. Mirko는 각 이동 전에 노드 \(X\)가 어디에 있었는지는 알 수 없고, 어디로 이동했는지만 알 수 있기 때문이다.

충격에서 아직 회복 중인 Mirko를 위해, Mirko의 기록으로 만들어진 상태에서 리스트의 초기 상태를 복원하는 최소 길이의 이동 수열을 찾는 프로그램을 작성하시오.

입력의 첫째 줄에 두 정수 \(N\)과 \(M\) (\(1 \le N, M \le 100000\))이 주어진다. 노드의 개수와 Mirko가 한 이동의 횟수이다.

다음 \(M\)개의 줄에는 Mirko가 한 이동이 하나씩 주어진다. 이동의 종류(A 또는 B)와 두 정수 \(X\), \(Y\)이다.

첫째 줄에 최소 이동 횟수(이 수를 \(R\)이라 하자)를 출력한다.

다음 \(R\)개의 줄에는 입력과 같은 형식으로 이동을 하나씩 출력한다.

참고: 이동 수열은 유일하지 않을 수 있다.

채점

횟수 \(R\)과 이동 수열이 모두 올바르면 해당 테스트 케이스에서 만점을 받는다. 올바른 \(R\)을 출력했지만 이동 수열을 출력하지 않았거나 이동 수열이 올바르지 않으면, 해당 테스트 케이스 점수의 절반을 받는다.

riseoj 작성

출처 COCI 2006/2007 Contest 3