[POI2009] TAB-Arrays

题意翻译

多组数据(不超过 $10$ 组),每组数据给出两个 $n$ 行 $m$ 列的矩阵 ($n,m\leq 1000$),保证每个矩阵内元素互不相同且权值均在 $[-10^6,10^6]$ 之间,你需要报告能否把其中一个矩阵通过若干次交换两行或者交换两列的操作变成另外一个矩阵。 单个读入数据可达 130MB 左右,请优化读入效率。

题目描述

Let us consider an array of size ![](http://main.edu.pl/images/OI16/tab-en-tex.1.png) filled with pairwise different integers. The following operations are allowed on the array: interchanging two rows, interchanging two columns. We call two arrays alike if one of them can be obtained from the other by a sequence of aforementioned operations. Write a programme that for a given set of pairs of arrays tells which pairs are alike.

输入输出格式

输入格式


The first line of the standard input contains one integer ![](http://main.edu.pl/images/OI16/tab-en-tex.2.png) (![](http://main.edu.pl/images/OI16/tab-en-tex.3.png)) denoting the number of pairs of arrays. Then descriptions of successive array pairs follow in subsequent lines. Each description starts with a line holding two integers ![](http://main.edu.pl/images/OI16/tab-en-tex.4.png) and ![](http://main.edu.pl/images/OI16/tab-en-tex.5.png) (![](http://main.edu.pl/images/OI16/tab-en-tex.6.png)), separated by a single space, that denote the common number of rows and columns of the arrays, respectively. The ![](http://main.edu.pl/images/OI16/tab-en-tex.7.png) lines that follow describe the first array. In the ![](http://main.edu.pl/images/OI16/tab-en-tex.8.png)-th of them there are ![](http://main.edu.pl/images/OI16/tab-en-tex.9.png) integers ![](http://main.edu.pl/images/OI16/tab-en-tex.10.png) (![](http://main.edu.pl/images/OI16/tab-en-tex.11.png)), separated by single spaces…

输出格式


Your programme should print out ![](http://main.edu.pl/images/OI16/tab-en-tex.19.png) lines to the standard output. The ![](http://main.edu.pl/images/OI16/tab-en-tex.20.png)-th of these should hold one word: "TAK" (yes in Polish) if the arrays of the ![](http://main.edu.pl/images/OI16/tab-en-tex.21.png)-th pair are alike, or "NIE" (no in Polish) otherwise.

输入输出样例

输入样例 #1

2
4 3
1 2 3
4 5 6
7 8 9
10 11 12
11 10 12
8 7 9
5 4 6
2 1 3
2 2
1 2
3 4
5 6
7 8

输出样例 #1

TAK
NIE