P6319 [COCI 2006/2007 #3] LISTA

Mirko 收到了一份礼物——一个崭新的双向链表！

这个长度为 $n$ 的链表包含 $1\sim n$ 这 $n$ 个节点，从左到右排列。 可以对这个链表执行两种操作： - `A x y`：把 $x$ 节点放到 $y$ 节点前。 - `B x y`：把 $x$ 节点放到 $y$ 节点后。 #### 例如：  这是一个有 $6$ 个节点的链表的初始状态。  这是进行操作 `A 1 4` 后的链表状态。  这是再进行操作 `B 3 5` 后的链表状态。 Mirko 把这个链表玩了几个小时。每进行一次操作，他都会在纸上记录下来。 当他兴致已尽，打算把链表恢复时，他惊讶地发现自己不知道最快的恢复方法，因为他只知道这些节点的结束位置。 请你运用 `A` `B` 两个操作，找出操作数最少的恢复方案并输出每一次的操作。

输入第一行为两个整数 $n,k$，表示链表的节点个数和 Mirko 的操作次数。 接下来的 $k$ 行，每行描述一个 Mirko 在纸上记录下来的操作，格式如题目描述所示。

输出第一行为一个整数 $K$，表示最少的恢复方案。 接下来的 $K$ 行，每行描述一个恢复时的操作，格式与输入相同。

#### 数据规模与约定 对于 $100\%$ 的数据，$2\le n\le 5\times 10^5$，$0\le k\le 1\times 10^5$。 #### 说明 **题目译自 [COCI2006-2007](https://hsin.hr/coci/archive/2006_2007/) [CONTEST #3](https://hsin.hr/coci/archive/2006_2007/contest3_tasks.pdf) *T6 BICIKLI*** 感谢 @[andyli](https://www.luogu.com.cn/user/84282) 提供SPJ。