[AdditionalFile5106.zip](file://AdditionalFile5106.zip?type=additional_file)

#5106. 「POI2009 R3」矩阵 Matrix

标签: 传统 | 时间限制: 21000 ms | 内存限制: 32 MiB |

题目描述

题目译自 XVI OI Olimpiada Informatyczna – III etap Tablice

考虑一个尺寸为 $n \times m$ 的矩阵，填满两两不同的整数。在此矩阵上，可执行以下操作：

1. 交换任意两行。
2. 交换任意两列。

若通过对一个矩阵执行若干次上述操作，可将其转换为另一个矩阵，则称这两矩阵相似。

编写程序，对于给定的矩阵对集合，判断哪些矩阵对包含相似的矩阵。

输入格式

第一行包含一个整数 $t$ $(1 \leq t \leq 10)$，表示矩阵对的数目。

接下来描述 $t$ 个矩阵对，每对描述如下：

第一行包含两个整数 $n, m$ $(1 \leq n, m \leq 1000)$，分别表示两矩阵的行数和列数。

接下来的 $n$ 行描述第一个矩阵，第 $i$ 行包含 $m$ 个整数 $a_{i,j}$ $(-1000000 \leq a_{i,j} \leq 1000000)$，表示第一矩阵第 $i$ 行元素。

再接下来的 $n$ 行描述第二个矩阵，第 $i$ 行包含 $m$ 个整数 $b_{i,j}$ $(-1000000 \leq b_{i,j} \leq 1000000)$，表示第二矩阵第 $i$ 行元素。

每个矩阵内的所有数字两两不同。

输出格式

输出 $t$ 行，若第 $k$ 对输入的矩阵相似，在第 $k$ 行输出 TAK，否则输出 NIE。

样例

输入

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

输出

TAK
NIE

第一对矩阵是相似的。要将第一个矩阵转换为第二个矩阵，只需先交换前两列，再将第一行与最后一行交换，然后将第二行与第三行交换。

第二对矩阵不相似，只需观察即可发现，它们的单元格值集合不同。