P18430 [CodeChef] CONCATPAL
普及
题目描述

Chef has two strings A and B of lengths N and M respectively.

Chef can rearrange both strings in any way he wants. Let the rearranged string of A be A' and the rearranged string of B be B'.

Determine whether we can construct rearrangements A' and B' such that (A' + B') is a palindrome.

Here + denotes the concatenation operation. For e.g. {abc} + {xyz} = {abcxyz}.

Note: A string is called palindrome if it reads the same backwards and forwards, for $e.g. \texttt{noon}$ and $\texttt{level}$ are palindromic strings.

------ Input Format ------

  • The first line contains a single integer T — the number of test cases. Then the test cases follow.
  • The first line of each test case contains two integers N and M — the length of the strings A and B respectively.
  • The second line of each test case contains a string A of length N containing lowercase Latin letters only.
  • The third line of each test case contains a string B of length M containing lowercase Latin letters only.

------ Output Format ------

For each test case, output YES if we can rearrange A and B such that (A' + B') becomes a palindrome. Otherwise, output NO.

You may print each character of YES and NO in uppercase or lowercase (for example, yes, yEs, Yes will be considered identical).

------ Constraints ------

$1 ≤ T ≤ 10^{5}$
$1 ≤ N, M ≤ 2 \cdot 10^{5}$
$A$ and $B$ consist of lowercase Latin letters only.
- The sum of $N + M$ over all test cases does not exceed $2 \cdot 10^{5}$.

----- Sample Input 1 ------
4
5 2
abcdd
ac
3 3
abc
xyz
2 4
aa
aaaa
1 3
a
aax

----- Sample Output 1 ------
YES
NO
YES
NO

----- explanation 1 ------
Test case $1$: We can rearrange $A$ to $A' = acdbd$ and $B$ to $B' = ca$. So $A' + B' = acdbdca$ which is palindromic.

Test case $2$: We can not rearrange $A$ and $B$ such that $A' + B'$ is palindromic.

Test case $3$: For $A' = aa$ and $B' = aaaa$, $A' + B' = aaaaaa$ is palindromic.

输入格式

见题面

输出格式

见题面

样例输入
4 5 2 abcdd ac 3 3 abc xyz 2 4 aa aaaa 1 3 a aax
样例输出
YES NO YES NO