题目描述

这是一个很古老的游戏了：有一个 $3 \times 3$ 的活动拼盘（如下图），方格上写有 $0 \sim 8$ 这九个数字。例如：

$$\begin{array}{|c|c|c|} \hline 3 & 7 & 5 \\ \hline 2 & 6 & 1 \\ \hline 4 & 8 & 0 \\ \hline \end{array}$$

利用拼盘背后的旋钮，游戏者每次可以进行以下两种操作之一：

1. 将拼盘外围的 $8$ 个方格按顺时针挪一个位置。
2. 将中间一行向右移动一个位置，最右边的方格被移到最左边。

例如：

$$\begin{array}{|c|c|c|} \hline 3 & 7 & 5 \\ \hline 2 & 6 & 1 \\ \hline 4 & 8 & 0 \\ \hline \end{array} \xrightarrow{\text{进行操作 1}} \begin{array}{|c|c|c|} \hline 2 & 3 & 7 \\ \hline 4 & 6 & 5 \\ \hline 8 & 0 & 1 \\ \hline \end{array} \xrightarrow{\text{进行操作 2}} \begin{array}{|c|c|c|} \hline 2 & 3 & 7 \\ \hline 5 & 4 & 6 \\ \hline 8 & 0 & 1 \\ \hline \end{array}$$

给你一个拼盘的初始状态，你能用最少的操作次数把拼盘变成下图所示的目标状态吗？

$$\begin{array}{|c|c|c|} \hline 0 & 1 & 2 \\ \hline 3 & 4 & 5 \\ \hline 6 & 7 & 8 \\ \hline \end{array}$$

输入格式

输入文件中包含三行三列九个数，同行的相邻两数用空格隔开，表示初始状态每个方格上的数字。初始状态不会是目标状态。

输出格式

如果目标状态无法达到，则输出“UNSOLVABLE”（引号不输出）。

否则，第一行是一个整数 $S$，表示最少的操作次数。接下来 $4 \times (S + 1)$ 行，每四行表示一个状态：前三行每行三个整数，相邻两数用空格隔开，表示每个方格上的数字，第四行是一个空行，作为分隔。第一个状态必须是初始状态，最后一个状态必须是目标状态。

2 3 0
1 8 7
5 4 6

4
2 3 0
1 8 7
5 4 6

1 2 3
5 8 0
4 6 7

1 2 3
0 5 8
4 6 7

0 1 2
4 5 3
6 7 8

0 1 2
3 4 5
6 7 8

提示

由@FlierKing提供SPJ