/ 
実行時間制限: 2 sec / メモリ制限: 1024 MiB
配点 : 800 点
問題文
A, B からなる長さ N の文字列 X,Y が与えられます．X の i 文字目を X_i と表すことにします．
以下の操作を 0 回以上 \left\lfloor \frac{N}{2} \right\rfloor 回以下行うことで， X を Y に一致させることができるか否かを判定してください．
- 1\leq l < r \leq N かつ X_l=
Aかつ X_r=Bなる整数組 (l, r) を選ぶ．X の l 番目から r 番目までの要素を反転する．ここで，「X の l 番目から r 番目までの要素を反転する」とは， X_l,X_{l+1},\ldots,X_{r-1},X_r を X_r,X_{r-1},\ldots,X_{l+1},X_l に同時に置き換えることを言う．
X を Y に一致させることが可能な場合には，そのような手順をひとつ出力してください．
T 個のテストケースが与えられるので，それぞれについて答えを求めてください．
制約
- 1 \leq T \leq 2.5\times 10^5
- 2 \leq N \leq 5\times 10^5
- 一つのテストケースに含まれる N の総和は 5\times 10^5 以下
- X,Y は
A,Bからなる長さ N の文字列 - 入力される数値は全て整数
入力
入力は以下の形式で標準入力から与えられる．
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
各テストケースは以下の形式で与えられる．
N X Y
出力
\mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T に対する答えを順に以下の形式で出力せよ．
0 回以上 \left\lfloor \frac{N}{2} \right\rfloor 回以下の操作で X を Y に一致させることが不可能な場合には，No と出力せよ．
可能な場合には，操作手順を次の形式で出力せよ．
Yes K l_1 r_1 l_2 r_2 \vdots l_K r_K
ここで K は操作回数で，l_i,r_i は i 回目の操作で選ぶ整数 l,r を表す．これらは次を満たす必要がある．
- 0 \leq K \leq \left\lfloor \frac{N}{2} \right\rfloor
- 1 \leq l_i < r_i \leq N
条件を満たす操作手順が複数存在する場合には，そのどれを出力しても正解と見なされる．
入力例 1
3 5 ABAAB ABBAA 4 AAAA BBBB 10 BABBAABBAA BBBBAAABAA
出力例 1
Yes 1 3 5 No Yes 3 2 7 4 6 3 5
1 番目のテストケースでは，X_3= A かつ X_5= B なので，X の 3 番目から 5 番目までの要素を反転する操作を行うことができます．この操作を行うと， X は ABBAA になり，Y と一致します．
2 番目のテストケースでは，どのように操作を行っても X を Y に一致させることができません．
Score : 800 points
Problem Statement
You are given strings X and Y of length N consisting of A and B. Let X_i denote the i-th character of X.
Determine whether it is possible to make X equal to Y by performing the following operation between 0 and \left\lfloor \frac{N}{2} \right\rfloor times, inclusive.
- Choose a pair of integers (l, r) such that 1\leq l < r \leq N, X_l=
A, and X_r=B. Reverse the elements of X from the l-th to the r-th position. Here, "reversing the elements of X from the l-th to the r-th position" means simultaneously replacing X_l,X_{l+1},\ldots,X_{r-1},X_r with X_r,X_{r-1},\ldots,X_{l+1},X_l.
If it is possible to make X equal to Y, output one such sequence of operations.
T test cases are given; solve each of them.
Constraints
- 1 \leq T \leq 2.5\times 10^5
- 2 \leq N \leq 5\times 10^5
- The sum of N over all test cases is at most 5\times 10^5.
- X and Y are strings of length N consisting of
AandB. - All input values are integers.
Input
The input is given from Standard Input in the following format:
T
\mathrm{case}_1
\mathrm{case}_2
\vdots
\mathrm{case}_T
Each test case is given in the following format:
N X Y
Output
Output the answers for \mathrm{case}_1,\mathrm{case}_2,\ldots,\mathrm{case}_T in this order in the following format.
If it is impossible to make X equal to Y using between 0 and \left\lfloor \frac{N}{2} \right\rfloor operations, inclusive, output No.
If it is possible, output a sequence of operations in the following format:
Yes K l_1 r_1 l_2 r_2 \vdots l_K r_K
Here K is the number of operations, and l_i, r_i are the integers l, r chosen in the i-th operation. These must satisfy the following:
- 0 \leq K \leq \left\lfloor \frac{N}{2} \right\rfloor
- 1 \leq l_i < r_i \leq N
If there are multiple valid sequences of operations, any of them will be accepted.
Sample Input 1
3 5 ABAAB ABBAA 4 AAAA BBBB 10 BABBAABBAA BBBBAAABAA
Sample Output 1
Yes 1 3 5 No Yes 3 2 7 4 6 3 5
In the first test case, X_3= A and X_5= B, so we can perform the operation of reversing the elements of X from the 3-rd to the 5-th position. After this operation, X is ABBAA, which equals Y.
In the second test case, it is impossible to make X equal to Y regardless of the operations performed.