P17825 [COCI 2026/2027 #1] 三堆箱子 / Tri

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$。 如果存在多个解，输出**任意一个**即可。

### 样例 1 解释 编号为 $1$ 的箱子位于堆顶，在编号为 $2$ 的箱子上方。Ana 先将箱子 $1$ 移到第 $2$ 堆，再将箱子 $2$ 移到第 $3$ 堆。随后，她将箱子 $1$ 放回第 $1$ 堆，再把箱子 $2$ 放到它上面。这样，箱子 $1$ 位于底部，箱子 $2$ 位于顶部。 ### 样例 2 解释 我们用一个**从下到上**的编号序列表示每一堆的内容。最初，第 $1$ 堆为 $[3,1,2]$，所以编号为 $2$ 的箱子位于堆顶，第 $2$ 堆和第 $3$ 堆均为空。下表给出了每次操作后各堆的状态： | 操作 | 第 1 堆 | 第 2 堆 | 第 3 堆 | | --- | --- | --- | --- | | $1 \to 2$ | $[3,1]$ | $[2]$ | $[\,]$ | | $1 \to 3$ | $[3]$ | $[2]$ | $[1]$ | | $1 \to 2$ | $[\,]$ | $[2,3]$ | $[1]$ | | $3 \to 1$ | $[1]$ | $[2,3]$ | $[\,]$ | | $2 \to 3$ | $[1]$ | $[2]$ | $[3]$ | | $2 \to 1$ | $[1,2]$ | $[\,]$ | $[3]$ | | $3 \to 1$ | $[1,2,3]$ | $[\,]$ | $[\,]$ | 第七次操作后，第 $1$ 堆中的箱子从下到上依次为 $1,2,3$，第 $2$ 堆和第 $3$ 堆均为空，因此排列正确。这既不是唯一正确的操作序列，也不是操作次数最少的序列。 ### 样例 3 解释 第 $1$ 堆中的箱子已经从下到上依次为 $1,2,3,4$，第 $2$ 堆和第 $3$ 堆均为空。这正是 Ana 想要的排列，因此不需要进行任何操作，$K=0$ 是一个正确答案。 ### 评分方式 | 子任务 | 分值 | 附加限制 | | --- | --- | --- | | 1 | 18 | $n \le 5$，$M=1000$ | | 2 | 31 | $M=260\,000$ | | 3 | 54 | $M=12\,500$ | | 4 | 7 | $M=5000$ |