Codeforces Round #598 (Div. 3) F. Equalizing Two Strings

You are given two strings ss and tt both of length nn and both consisting of lowercase Latin letters.

In one move, you can choose any length lenlen from 11 to nn and perform the following operation:

• Choose any contiguous substring of the string ss of length lenlen and reverse it;
• at the same time choose any contiguous substring of the string tt of length lenlen and reverse it as well.

Note that during one move you reverse exactly one substring of the string ss and exactly one substring of the string tt.

Also note that borders of substrings you reverse in ss and in tt can be different, the only restriction is that you reverse the substrings of equal length. For example, if len=3len=3 and n=5n=5, you can reverse s[1…3]s[1…3] and t[3…5]t[3…5], s[2…4]s[2…4] and t[2…4]t[2…4], but not s[1…3]s[1…3] and t[1…2]t[1…2].

Your task is to say if it is possible to make strings ss and tt equal after some (possibly, empty) sequence of moves.

You have to answer qq independent test cases.

Input

The first line of the input contains one integer qq (1≤q≤1041≤q≤104) — the number of test cases. Then qq test cases follow.

The first line of the test case contains one integer nn (1≤n≤2⋅1051≤n≤2⋅105) — the length of ss and tt.

The second line of the test case contains one string ss consisting of nn lowercase Latin letters.

The third line of the test case contains one string tt consisting of nn lowercase Latin letters.

It is guaranteed that the sum of nn over all test cases does not exceed 2⋅1052⋅105 (∑n≤2⋅105∑n≤2⋅105).

Output

For each test case, print the answer on it — "YES" (without quotes) if it is possible to make strings ss and tt equal after some (possibly, empty) sequence of moves and "NO" otherwise.

Example

input

Copy

4
4
abcd
abdc
5
ababa
baaba
4
asdf
asdg
4
abcd
badc

output

Copy

NO
YES
NO
YES

大概意思

现在给你两个字符串，你可以进行若干次操作。

每次操作需要在每个字符串都选择出长度为len的一个区间，两个区间位置不一定相同，然后将这个区间的字符都进行翻转。

问你进行若干次操作后，这俩字符串能变成一样的吗？

#include<bits/stdc++.h>
using namespace std;
int n;
string s1,s2,S1,S2;
//前两个满足， 如果两个字符串的逆的奇偶性相同，那么一定是YES
//在判断1和2之后，我们得到的一定是一个排列，问题就变成你可以翻转若干次，两个排列能否相同。
//我们考虑我们同时翻转相同长度的，我们排列的逆一定会发生奇偶性的变化，
//那么如果一开始奇偶性就不同，那么不管怎么翻转，都不会相同。
int Count(string s) {
    int num=0;
    for(int i=0; i<s.size(); i++) {
        for(int j=0; j<i; j++) {
            if(s[j]>s[i])
                num++;
        }
    }
    return num;
}
void solve() {
    cin>>n>>S1>>S2;
    s1=S1;
    s2=S2;
    sort(s1.begin(),s1.end());
    sort(s2.begin(),s2.end());
    for(int i=0; i<n; i++) {
        if(s1[i]!=s2[i]) { //如果存在不同字符，那么一定不行
            puts("NO");
            return;
        }
    }
    for(int i=1; i<n; i++) {
        if(s1[i]==s1[i-1]) {//如果存在相同字符
            puts("YES");
            return;
        }
        if(s2[i]==s2[i-1]) {
            puts("YES");
            return;
        }
    }
    if(Count(S1)%2==Count(S2)%2) {
        puts("YES");
    } else {
        puts("NO");
    }
    return;
}
int main() {
    int t;
    scanf("%d",&t);
    while(t--)solve();
}