Checker for Array Shuffling

题意翻译

给定一个长为 $n$ 的数组 $a$。若 $a$ 的一个排列 $b$ 可以通过 $k$ 次将任意两个数交换位置得到 $a$，则 $b$ 的价值为所有合法 $k$ 的最小值。 现在给出 $a$ 的某个排列 $b$，判断它的价值是否为所有长为 $n$ 的数组的最大值。若是则输出 `AC` ，否则输出 `WA` 。$t$ 组数据。 $t\le 10^4$，$n\le 2\cdot 10^5$，$1\le a_i,b_i \le n$。

题目描述

oolimry has an array $ a $ of length $ n $ which he really likes. Today, you have changed his array to $ b $ , a permutation of $ a $ , to make him sad. Because oolimry is only a duck, he can only perform the following operation to restore his array: - Choose two integers $ i,j $ such that $ 1 \leq i,j \leq n $ . - Swap $ b_i $ and $ b_j $ . The sadness of the array $ b $ is the minimum number of operations needed to transform $ b $ into $ a $ . Given the arrays $ a $ and $ b $ , where $ b $ is a permutation of $ a $ , determine if $ b $ has the maximum sadness over all permutations of $ a $ .

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 10^4 $ ) — the number of test cases. The description of the test cases follows. The first line of each test case contains a single integer $ n $ ( $ 1 \leq n \leq 2 \cdot 10^5 $ ) — the length of the array. The second line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq n $ ) — the elements of the array $ a $ . The third line of each test case contains $ n $ integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \leq b_i \leq n $ ) — the elements of the array $ b $ . It is guaranteed that $ b $ is a permutation of $ a $ . It is guaranteed that the sum of $ n $ over all test cases does not exceed $ 2 \cdot 10^5 $ .

输出格式

For each test case, print "AC" (without quotes) if $ b $ has the maximum sadness over all permutations of $ a $ , and "WA" (without quotes) otherwise.

输入输出样例

输入样例 #1

4
2
2 1
1 2
4
1 2 3 3
3 3 2 1
2
2 1
2 1
4
1 2 3 3
3 2 3 1

输出样例 #1

AC
AC
WA
WA

说明

In the first test case, the array $ [1,2] $ has sadness $ 1 $ . We can transform $ [1,2] $ into $ [2,1] $ using one operation with $ (i,j)=(1,2) $ . In the second test case, the array $ [3,3,2,1] $ has sadness $ 2 $ . We can transform $ [3,3,2,1] $ into $ [1,2,3,3] $ with two operations with $ (i,j)=(1,4) $ and $ (i,j)=(2,3) $ respectively. In the third test case, the array $ [2,1] $ has sadness $ 0 $ . In the fourth test case, the array $ [3,2,3,1] $ has sadness $ 1 $ .