问题 K: Scheming Furry

链接：https://ac.nowcoder.com/acm/contest/57362/K
来源：牛客网
The Animals Corporation has assigned a new task with codename S to its staff!

The fox and the cat have received an unsorted matrix $A$ with $n$ rows and $m$ columns. The elements of the matrix (Ai,jA_{i,j}Ai,j) are integers from $1$ to $n\times m$ and are pairwise distinct. Their mission is to make the matrix sorted. Here we call matrix $A$ sorted, if and only if its elements are non-decreasing in reading order (i.e., A1,1≤A1,2≤⋯≤A1,m≤A2,1≤A2,2≤⋯A2,m≤⋯≤An,1≤An,2≤⋯≤An,mA_{1,1} \le A_{1,2} \le \cdots \le A_{1,m} \le A_{2,1} \le A_{2,2} \le \cdots A_{2,m} \le \cdots \le A_{n,1} \le A_{n,2} \le \cdots \le A_{n,m}A1,1≤A1,2≤⋯≤A1,m≤A2,1≤A2,2≤⋯A2,m≤⋯≤An,1≤An,2≤⋯≤An,m).

To finish the task, the furry groupmates have a clear division of labor. Specifically, the fox can only perform the following operation:

• Choose integers i,ji,ji,j (1≤i<j≤n1 \le i < j \le n1≤i<j≤n), and swap the $i$-th row and the $j$-th row of matrix $A$.

And the cat can only perform the following operation:

The groupmates operate in turn (The fox goes first, the cat next, then the fox again, and so on). In their turn, one is not allowed to perform multiple operations or give up performing the operation.

It is a golden opportunity to develop team spirit. However, both the fox and the cat desire to win their boss's favor by becoming the first one who makes the matrix sorted after his own operation. And what's worse is that, if one knows he has no chance of meeting such desire, he will try to prevent his groupmate from being the first to sort the matrix, even if the matrix will remain unsorted forever!

You, a mysterious staff member, have seen through their charade. Assuming both the fox and the cat are clever enough, you wonder who will be the first to make the matrix sorted.

The first line contains an integer $T$ (1≤T≤1001 \le T \le 1001≤T≤100), denoting the number of test cases.
For each test case:
The first line contains two integers $n$ and $m$ ($2\le n,m\le 200$).
Then $n$ lines follow, the $i$-th of which contains $m$ integers Ai,1,Ai,2,…,Ai,mA_{i,1},A_{i,2},\ldots,A_{i,m}Ai,1,Ai,2,…,Ai,m (1≤Ai,j≤n×m1 \le A_{i,j} \le n\times m1≤Ai,j≤n×m).
It is guaranteed that in each test case, matrix $A$ is initially unsorted and its elements are pairwise distinct.

For each test case, print "FOX" or "CAT" in one line, indicating who will be the first to make the matrix sorted. If the matrix will be unsorted forever, print "NSFW" in one line (indicating the boss will be irritated and fire some staff members slack in work).

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

FOX
NSFW
CAT

In the first test case, the fox will swap the first row and the second row. Then, the matrix will be sorted.
The second test case gives a special case: no matter how the fox and the cat perform operations, the matrix is impossible to be sorted by any of them. So it will certainly be unsorted forever.