题目描述

Erast Kopi is famous Sudoku puzzle designer. Resounding success of his puzzle compilations caused a number of imitations and plagiarisms. Prior to sending a lawsuit he decided to get more evidence.

Sudoku puzzle is a table $9 \times 9$ , divided into $3 \times 3$ subtables of $3 \times 3$ cells each. Each cell may contain a digit from $1$ to $9$ . The task is to fill empty cells with digits in a way that each row, each column and each of the $9$ subtables $3 \times 3$ contains each digit from $1$ to $9$ exactly once.

Kopi has a database of Sudoku puzzles and he wants to check if it contains similar puzzles. The puzzle $P$ is similar to the puzzle $Q$ , if it is possible to transform the puzzle $P$ into the puzzle $Q$ using a sequence of the following operations:

choose two digits $x$ and $y$ and replace all digits $x$ with $y$ and vice versa;

swap two triples of rows: $(1 , 2 , 3) , (4 , 5 , 6) , (7 , 8 , 9)$ ;

swap two rows in one triple of rows;

swap two triples of columns: $(1 , 2 , 3) , (4 , 5 , 6) , (7 , 8 , 9)$ ;

swap two columns in one triple of columns;

flip along top-left -- bottom-right axis. After this operation columns become rows and vice versa.

Help Kopi to find similar puzzles in his database.

输入格式

The first line of the input contains single integer $n$ -- the number of puzzles in the database $(1 \le n \le 20)$ .

The rest of the input contains description of $n$ puzzles: $P_1 , P_2$ , . . . , Pn. Each puzzle is described by nine lines that contain nine characters each. Each character is either a digit from $1$ to $9$ , or a dot $(‘. ')$ denoting an empty cell. An empty line separates consecutive puzzles in the database.

There are no spaces in the input file.

The puzzles are not guaranteed to be solvable.

输出格式

Check if the puzzle $P_1$ is similar to puzzles $P_2$ , P3 , . . . , $P_n$ (in this order), than check if the puzzle $P_2$ is similar to puzzles P3 , P4 , . . . , $P_n$ (in this order) and so on.

If the puzzle $P_i$ is similar to the puzzle $Pj (1 \le i < j \le n)$ output Yes, otherwise output No. If the answer is positive, the next line should contain an integer qij -- the number of operations required to transform the puzzle $P_i$ to the puzzle $Pj$ . The number of operations is not required to be minimal, however it must not exceed $1000$ . In the following qij lines write the operations that transform the puzzle $P_i$ to the puzzle $Pj$ , one per line.

Operations are encoded in the following way:

D $x$ y for swapping digits $x$ and $y$ ;

R a b for swapping triples of rows (3a $− 2$ , 3a $− 1 , 3a)$ and (3b $− 2$ , 3b $− 1 , 3b);$

r a b for swapping rows a and $b$ , rows must belong to same triple of rows;

C a b for swapping triples of columns (3a $− 2$ , 3a $− 1 , 3a)$ and (3b $− 2$ , 3b $− 1 , 3b);$

c a b for swapping columns a and $b$ , columns must belong to same triple of columns;

F for flipping along top-left -- bottom-right axis.

The columns are numbered from left to right and the rows are numbered from top to bottom as they are given in the input file, starting from one.

题目大意

对于两个 $9\times9$ 数独谜题（不管是否有解）$A,B$，定义 $A$ 和 $B$ 等价当且仅当 $A$ 可以通过下列操作进行若干次变换后成为 $B$。

• 选择两个数字 $x,y$，将所有 $x$ 变成 $y$，所有 $y$ 变成 $x$。
• 在 $(1,2,3),(4,5,6),(7,8,9)$ 三个三元组中，选择两个，作为整体交换以它为下标的行。
• 选择在同一个三元组中的两个数 $x,y$，交换谜题的第 $x$ 行和第 $y$ 行。
• 在 $(1,2,3),(4,5,6),(7,8,9)$ 三个三元组中，选择两个，作为整体交换以它为下标的列。
• 选择在同一个三元组中的两个数 $x,y$，交换谜题的第 $x$ 列和第 $y$ 列。
• 把 $A$ 转置。

现在给定 $n(n\le20)$ 个数独谜题，判断它们两两是否等价。若等价，还需要输出一种变换的方法。D x y 表示将两个数字交换，R a b 表示整体交换三元组 $(3a-2,3a-1,3a),(3b-2,3b-1,3b)$ 对应的行，r a b 表示交换两个行，同理有 C a b 和 c a b 作为列操作。F 表示取转置。

translated by @Starlight237

4
.....1...
1........
.2.....8.
.........
8....9...
.........
....7....
...2...1.
2...4....

....2....
...7.4...
8.......9
.8...2..1
..2......
.........
.........
..1.8....
.........

1........
.........
.........
.........
.........
.........
.........
.........
.........

.....1...
1........
.2.....8.
.........
8....9...
.........
....7....
...2...1.
2...4....

Yes
7
C 1 2
D 5 3
F
r 7 9
c 6 5
C 2 3
D 1 8
No
Yes
0
No
Yes
8
R 1 2
C 2 3
c 4 5
F
r 5 6
c 7 9
D 1 8
D 3 5
No

提示

Time limit: 2 s, Memory limit: 256 MB.