BLOCKS - Arranging the Blocks

no tags 

A group of n children are playing with a set of n2 flat square blocks. Each block is painted from above with one colour, and there are no more than 2 blocks of each colour. The blocks are initially arranged in an n x n square forming some sort of picture.

The children have been provided with some other n x n picture and asked to rearrange the blocks to that form. Since this is not really what they enjoy doing most, they intend to solve the task together and spend as little time on it as possible. Thus, every minute each child chooses a single 1 x n row or n x 1 column of blocks to rearrange. This row/column may never intersect with rows/columns chosen by other children in the same minute. A child takes one minute to perform any rearrangement (permutation) of the blocks within its row/column it likes.

Determine whether the children can perform their task of converting one block image into the other, and if so -- find the minimum possible time in minutes required to achieve this.


The input starts with a line containing a single integer t<=200, the number of test cases. t test cases follow. Each test case begins with a line containing integer n (1<=n<=500). The next n lines contain n integers Pi,j each, forming a bitmap matrix representing the colours of the blocks in their initial configuration (1<=Pi,j<=n2). The following n lines contain n integers Qi,j each, corresponding to the matrix for the final configuration (1<=Qi,j<=n2).


For each test case output a line with a single non-negative integer corresponding to the number of minutes required to transform matrix P into matrix Q, or the word no if no such transformation is possible.


1 3 4
2 1 3
2 5 5
3 1 3
2 1 2
4 5 5
1 2 3
4 5 6
7 8 9
1 5 6
4 2 9
7 8 3
1 2
1 2
1 3
1 2


The actions taken in the first test case are illustrated below.

2 step transformation: 134 213 255 -> 413 312 255 -> 313 212 455

Warning: enormous Input/Output data, be careful with certain languages

Added by:adrian
Time limit:1.754s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: NODEJS PERL6 VB.NET
Resource:DASM Programming League 2004, problemset 4