P17825 [COCI 2026/2027 #1] Tri

Ana works in a warehouse that has **three piles of boxes**, labelled $1$, $2$ and $3$. Each box has a number from $1$ to $n$ written on it, and **every number appears on exactly one box**. At the beginning, all the boxes are stacked on top of each other on **pile $1$**, in some order, while piles $2$ and $3$ are empty. The boxes are heavy, so Ana moves them one at a time. In one move, she may **take the box from the top** of one pile and **put it on top** of a different pile. She must not touch a box that is not on top of its pile, or the pile would fall over. Ana wants **all the boxes to end up on pile $1$**, stacked **in increasing order from bottom to top**: the box with number $1$ at the bottom, the box with number $2$ on top of it, and so on, up to the box with number $n$ at the top. Piles $2$ and $3$ must be **empty** at the end. Ana is short on time, so she may make **at most $M$ moves**. Help her find a sequence of moves that achieves this arrangement. The number of moves **does not have to be the smallest possible**, but it must not be greater than $M$.

The first line contains positive integers $n$ and $M$ ($1 \le n \le 500$, $1000 \le M \le 260\,000$), the number of boxes and the **maximum allowed number of moves**. The second line contains $n$ distinct positive integers $p_1,p_2,\ldots,p_n$ ($1 \le p_i \le n$), the numbers written on the boxes on pile $1$, listed **from bottom to top**. In other words, $p_1$ is the number on the lowest box, and $p_n$ is the number on the box at the top of the pile.

In the first line, output an integer $K$ ($0 \le K \le M$), the **number of moves** Ana should make. In the $i$-th of the following $K$ lines, output two different numbers $a_i$ and $b_i$ ($a_i,b_i \in \{1,2,3\}$) describing the $i$-th move: Ana **takes the box from the top of pile $a_i$** and **puts it on top of pile $b_i$**. Pile $a_i$ must not be empty when the move is made. After all $K$ moves, the boxes on pile $1$ must be in the order $1,2,\ldots,n$ from bottom to top, and piles $2$ and $3$ must be empty. If the boxes are already stacked this way at the beginning, you may output $K=0$. If there are multiple solutions, output **any of them**.

#### Clarification of the first example The box with number $1$ is on top, above the box with number $2$. Ana first moves box $1$ to pile $2$, and then box $2$ to pile $3$. After that, she puts box $1$ back on pile $1$, and then box $2$ on top of it, so that box $1$ is at the bottom and box $2$ is at the top. #### Clarification of the second example We write the contents of each pile as a sequence of numbers **from bottom to top**. At the beginning, pile $1$ contains $[3,1,2]$, so the box with number $2$ is on top, and piles $2$ and $3$ are empty. The table shows the state of all piles after each move: | Move | Pile 1 | Pile 2 | Pile 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]$ | $[\,]$ | $[\,]$ | After the seventh move, pile $1$ contains boxes $1,2,3$ from bottom to top, and piles $2$ and $3$ are empty, so the arrangement is correct. This is not the only correct sequence of moves, nor is it the shortest one. #### Clarification of the third example The boxes on pile $1$ are already in the order $1,2,3,4$ from bottom to top, and piles $2$ and $3$ are empty. This is exactly the arrangement Ana wants, so she does not need to make any moves, and $K=0$ is a correct answer. #### Scoring | Subtask | Points | Constraints | | --- | --- | --- | | 1 | 18 | $n \le 5$, $M=1000$ | | 2 | 31 | $M=260\,000$ | | 3 | 54 | $M=12\,500$ | | 4 | 7 | $M=5000$ |