P6319 [COCI 2006/2007 #3] LISTA

Mirko received a gift—a brand-new doubly linked list.

This linked list of length $n$ contains $n$ nodes labeled $1\sim n$, arranged from left to right. Two types of operations can be performed on this linked list: - `A x y`: move node $x$ to be placed before node $y$. - `B x y`: move node $x$ to be placed after node $y$. #### Example  This is the initial state of a linked list with $6$ nodes.  This is the state after performing the operation `A 1 4`.  This is the state after then performing the operation `B 3 5`. Mirko played with the linked list for several hours. Every time he performed an operation, he wrote it down on paper. When he got tired and planned to restore the linked list, he was surprised to find that he did not know the fastest way to restore it, because he only knows the final positions of these nodes. Please use operations `A` and `B` to find a restoration plan with the minimum number of operations, and output each operation.

The first line contains two integers $n,k$, representing the number of nodes in the linked list and the number of operations Mirko performed. The next $k$ lines each describe an operation Mirko wrote down, in the format shown in the statement.

The first line outputs an integer $K$, representing the minimum number of operations in the restoration plan. The next $K$ lines each describe an operation during restoration, in the same format as the input.

#### Constraints For $100\%$ of the testdata, $2\le n\le 5\times 10^5$, $0\le k\le 1\times 10^5$. #### Notes **This problem is translated from [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T6 BICIKLI*.** Thanks to @[andyli](https://www.luogu.com.cn/user/84282) for providing the SPJ. Translated by ChatGPT 5