A - Replace C or Swap AB Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 400 点

問題文

A, B, C からなる長さ N の文字列 X, Y が与えられます．

X に対して次の 3 種の操作を（0 回を含め）何回でも行えるとき，X を Y と一致させることが可能であるか否かを判定してください．

  • 操作 (1)：X に含まれる文字 C をひとつ選び， A で置き換える．
  • 操作 (2)：X に含まれる文字 C をひとつ選び， B で置き換える．
  • 操作 (3)：X に含まれる部分文字列 AB をひとつ選び， BA で置き換える．より形式的には，X のうち i 文字目が A であり (i+1) 文字目が B であるような i を選び，X の i 文字目を B で，(i+1) 文字目を A で置き換える．

T 個のテストケースが与えられるので，それぞれについて答えを求めてください．

制約

  • 1\leq T\leq 2\times 10^5
  • 1\leq N\leq 2\times 10^5
  • X, Y は A, B, C からなる長さ N の文字列である．
  • 1 つの入力に含まれるテストケースについて，N の総和は 2\times 10^5 以下である．

入力

入力は以下の形式で標準入力から与えられます．

T
\text{case}_1
\vdots
\text{case}_T

各テストケースは以下の形式で与えられます．

N X Y

出力

T 行出力してください．i 行目には i 番目のテストケースについて，X を Y と一致させることが可能ならば Yes，不可能ならば No を出力してください．

入力例 1

6
3 ABC ABC
1 C B
1 B C
2 AB BA
2 BA AB
3 CCB ABA

出力例 1

Yes
Yes
No
Yes
No
Yes
  • 1 番目のテストケースについて： 0 回の操作により X を Y と一致させることが出来ます．
  • 2 番目のテストケースについて： 1 回の操作 (2) により X を Y と一致させることが出来ます．
  • 4 番目のテストケースについて： 1 回の操作 (3) により X を Y と一致させることが出来ます．
  • 6 番目のテストケースについて： 例えば操作 (1), 操作 (3), 操作 (1) をこの順に適切な位置に対して行うと，X は CCB → CAB → CBA → ABA と変化して，Y と一致します．

入力例 2

7
5 ABABA BABAB
5 ABCBC BBABA
5 CCCCC CBABC
5 BBAAA AAABB
5 AAABB BBAAA
5 ACACB BAACB
5 ACACB BBACA

出力例 2

No
Yes
Yes
No
Yes
Yes
No

Score : 400 points

Problem Statement

You are given strings X and Y of length N each, consisting of A, B, and C.

Determine if it is possible to make X coincide with Y by performing the following three kinds of operations on X any number of times, possibly zero.

  • Operation (1)：Choose a character C in X and replace it with A.
  • Operation (2)：Choose a character C in X and replace it with B.
  • Operation (3)：Choose a substring AB in X and replace it with BA. More formally, choose an i such that the i-th and (i+1)-th characters of X are A and B, respectively, and replace the former with B and the latter with A.

You have T test cases to solve.

Constraints

  • 1\leq T\leq 2\times 10^5
  • 1\leq N\leq 2\times 10^5
  • Each of X and Y is a string of length N consisting of A, B, and C.
  • The sum of N over the test cases in a single input is at most 2\times 10^5.

Input

The input is given from Standard Input in the following format:

T
\text{case}_1
\vdots
\text{case}_T

Each test case is given in the following format:

N X Y

Output

Print T lines. The i-th line should contain Yes if it is possible to make X coincide with Y for the i-th test case, and No otherwise.

Sample Input 1

6
3 ABC ABC
1 C B
1 B C
2 AB BA
2 BA AB
3 CCB ABA

Sample Output 1

Yes
Yes
No
Yes
No
Yes
  • For the first test case, you can perform the operations zero times to make X coincide with Y.
  • For the second test case, you can perform Operation (2) once to make X coincide with Y.
  • For the fourth test case, you can perform Operation (3) once to make X coincide with Y.
  • For the sixth test case, you can perform Operations (1), (3), (1) in this order at appropriate positions, for example, to make X change as CCB → CAB → CBA → ABA and coincide with Y.

Sample Input 2

7
5 ABABA BABAB
5 ABCBC BBABA
5 CCCCC CBABC
5 BBAAA AAABB
5 AAABB BBAAA
5 ACACB BAACB
5 ACACB BBACA

Sample Output 2

No
Yes
Yes
No
Yes
Yes
No