[POI2009] TAB-Arrays

题目描述

Let us consider an array of size 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.

给出两个n*m的矩阵，保证每个矩阵内元素互不相同且权值均在[-10^6,10^6]之间，请能否把其中一个矩阵通过若干次交换两行或者交换两列的操作变成另外一个矩阵

输入格式

The first line of the standard input contains one integer () denoting the number of pairs of arrays. 第一行正整数T(1≤T≤10)表示数据组数.

每组数据包括：第一行nm（1≤n,m≤1000）2个n行m列的整数矩阵，

元素绝对值均在10^6以内

Then descriptions of successive array pairs follow in subsequent lines.

Each description starts with a line holding two integers and (), separated by a single space, that denote the common number of rows and columns of the arrays, respectively.

The lines that follow describe the first array.

In the -th of them there are integers (), separated by single spaces…

输出格式

Your programme should print out lines to the standard output.

The -th of these should hold one word: "TAK" (yes in Polish) if the arrays of the -th pair are alike, or "NIE" (no in Polish) otherwise.

样例 #1

样例输入 #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