C. awoo‘s Favorite Problem--Educational Codeforces Round 130 (Rated for Div. 2)

Problem - 1697C - Codeforces

C. awoo's Favorite Problem

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given two strings ss and tt, both of length nn. Each character in both string is 'a', 'b' or 'c'.

In one move, you can perform one of the following actions:

• choose an occurrence of "ab" in ss and replace it with "ba";
• choose an occurrence of "bc" in ss and replace it with "cb".

You are allowed to perform an arbitrary amount of moves (possibly, zero). Can you change string ss to make it equal to string tt?

Input

The first line contains a single integer qq (1≤q≤1041≤q≤104) — the number of testcases.

The first line of each testcase contains a single integer nn (1≤n≤1051≤n≤105) — the length of strings ss and tt.

The second line contains string ss of length nn. Each character is 'a', 'b' or 'c'.

The third line contains string tt of length nn. Each character is 'a', 'b' or 'c'.

The sum of nn over all testcases doesn't exceed 105105.

Output

For each testcase, print "YES" if you can change string ss to make it equal to string tt by performing an arbitrary amount of moves (possibly, zero). Otherwise, print "NO".

Example

input

Copy

5
3
cab
cab
1
a
b
6
abbabc
bbaacb
10
bcaabababc
cbbababaac
2
ba
ab

output

Copy

YES
NO
YES
YES
NO

=========================================================================

ab ->ba

bc->cb

第一个置换只能有两个作用，那就是aaaab把b放到前面,abbbb把a放在后面

第二个置换同理

很自然的贪心。我们从末尾往前扫描，如果相等那么继续，否则，如果b对a，往前找a, c对b,往前找b，找不到或者不是这种配对，那么就无解。做多了感觉瞬间来。

# include <iostream>
# include<algorithm>
# include<cstring>
# include<vector>
# include<queue>
# define mod 1000000007

using namespace std;
typedef long long int ll;

int main()
{

   int t;
   cin>>t;

   while(t--)
   {
       int n;

       cin>>n;
       string s,t;

       cin>>s>>t;

       int flag=0;

       for(int i=n-1;i>=0;i--)
       {
           if(s[i]==t[i])
            continue;

           if(s[i]=='b'&&t[i]=='a')
           {

               int j;
               for( j=i-1;j>=0;j--)
               {
                   if(s[j]=='a'||s[j]=='b')
                   {
                       if(s[j]=='a')
                       {
                           swap(s[j],s[i]);

                           break;
                       }
                   }
                   else
                   {
                       flag=1;

                       break;

                   }
               }

               if(j==-1)
                flag=1;


           }
           else if(s[i]=='c'&&t[i]=='b')
           {
               int j;
               for( j=i-1;j>=0;j--)
               {
                   if(s[j]=='c'||s[j]=='b')
                   {
                       if(s[j]=='b')
                       {
                           swap(s[j],s[i]);

                           break;
                       }
                   }
                   else
                   {
                       flag=1;

                       break;
                   }
               }

               if(j==-1)
                flag=1;

           }
           else
           {
               flag=1;
               break;
           }
       }

       if(flag)
       {
           cout<<"NO"<<endl;

       }
       else
       {
           cout<<"YES"<<endl;
       }
   }


    return 0;
}