题目描述

Ana 在一座仓库工作，仓库中有三堆箱子，编号为 $1$、$2$、$3$。每个箱子上写着一个 $1$ 到 $n$ 之间的数，且每个数都恰好出现在一个箱子上。

最初，所有箱子按照某种顺序从下到上堆放在第 $1$ 堆中，第 $2$ 堆和第 $3$ 堆均为空。

箱子很重，因此 Ana 每次只能移动一个箱子。一次操作中，她可以取走某一堆最上面的箱子，并将其放到另一堆的最上面。她不能移动不在堆顶的箱子，否则整堆箱子就会倒下。

Ana 希望最终所有箱子都在第 $1$ 堆中，并且从下到上按编号递增的顺序堆放：编号为 $1$ 的箱子位于最底部，编号为 $2$ 的箱子放在它上面，依此类推，编号为 $n$ 的箱子位于最顶部。最终第 $2$ 堆和第 $3$ 堆必须均为空。

Ana 的时间很紧，因此她最多可以进行 $M$ 次操作。请帮助她找出一个能够实现上述排列的操作序列。操作次数不必最少，但不能超过 $M$。

输入格式

第一行包含两个正整数 $n$ 和 $M$（$1 \le n \le 500$，$1000 \le M \le 260\,000$），分别表示箱子数量和允许的最大操作次数。

第二行包含 $n$ 个互不相同的正整数 $p_1,p_2,\ldots,p_n$（$1 \le p_i \le n$），表示第 $1$ 堆中的箱子从下到上的编号。也就是说，$p_1$ 是最底部箱子的编号，$p_n$ 是最顶部箱子的编号。

输出格式

第一行输出一个整数 $K$（$0 \le K \le M$），表示 Ana 需要进行的操作次数。

接下来 $K$ 行，第 $i$ 行输出两个不同的数 $a_i$ 和 $b_i$（$a_i,b_i \in \{1,2,3\}$），描述第 $i$ 次操作：Ana 取走第 $a_i$ 堆最上面的箱子，并将其放到第 $b_i$ 堆的最上面。进行操作时，第 $a_i$ 堆必须非空。

完成全部 $K$ 次操作后，第 $1$ 堆中的箱子必须从下到上依次为 $1,2,\ldots,n$，第 $2$ 堆和第 $3$ 堆必须均为空。如果初始时箱子已经按这种方式排列，可以输出 $K=0$。

如果存在多个解，输出任意一个即可。

2 1000
2 1

4
1 2
1 3
2 1
3 1

3 1000
3 1 2

7
1 2
1 3
1 2
3 1
2 3
2 1
3 1

4 1000
1 2 3 4

0

提示

样例 1 解释

编号为 $1$ 的箱子位于堆顶，在编号为 $2$ 的箱子上方。Ana 先将箱子 $1$ 移到第 $2$ 堆，再将箱子 $2$ 移到第 $3$ 堆。随后，她将箱子 $1$ 放回第 $1$ 堆，再把箱子 $2$ 放到它上面。这样，箱子 $1$ 位于底部，箱子 $2$ 位于顶部。

样例 2 解释

我们用一个从下到上的编号序列表示每一堆的内容。最初，第 $1$ 堆为 $[3,1,2]$，所以编号为 $2$ 的箱子位于堆顶，第 $2$ 堆和第 $3$ 堆均为空。下表给出了每次操作后各堆的状态：

第七次操作后，第 $1$ 堆中的箱子从下到上依次为 $1,2,3$，第 $2$ 堆和第 $3$ 堆均为空，因此排列正确。这既不是唯一正确的操作序列，也不是操作次数最少的序列。

样例 3 解释

第 $1$ 堆中的箱子已经从下到上依次为 $1,2,3,4$，第 $2$ 堆和第 $3$ 堆均为空。这正是 Ana 想要的排列，因此不需要进行任何操作，$K=0$ 是一个正确答案。

评分方式