eolymp
bolt
Try our new interface for solving problems
Məsələlər

Intellectual Property

Intellectual Property

Zaman məhdudiyyəti 2 saniyə
Yaddaşı istafadə məhdudiyyəti 256 MiB

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 table9×9, divided into 3×3 subtables of 3×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×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.

Giriş verilənləri

The first line of the input contains single integer n — the number of puzzles in the database (1n20).

The rest of the input contains description of n puzzles: P_1, P_2, ..., P_n. 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.

Çıxış verilənləri

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

If the puzzle P_i is similar to the puzzle P_j (1i < jn) output "Yes", otherwise output "No". If the answer is positive, the next line should contain an integer q_ij — the number of operations required to transform the puzzle P_ito the puzzle P_j. The number of operations is not required to be minimal, however it must not exceed 1000. In the following q_ij lines write the operations that transform the puzzle P_i to the puzzle P_j, 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.

Nümunə

Giriş verilənləri #1
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....
Çıxış verilənləri #1
Yes
7
F
R 1 2
r 7 9
c 5 6
c 4 5
C 2 3
D 1 8
No
Yes
2
r 4 6
c 7 9
No
Yes
7
F
R 2 3
r 4 5
r 5 6
c 7 9
C 1 2
D 1 8
No
Mənbə ACM ICPC 2013–2014, NEERC, Northern Subregional Contest, St Petersburg, October 26, 2013