[Solution] Complementary XOR Codeforces Solution

C. Complementary XOR

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You have two binary strings 𝑎$a$ and 𝑏$b$ of length 𝑛$n$. You would like to make all the elements of both strings equal to 0$0$. Unfortunately, you can modify the contents of these strings using only the following operation:

• You choose two indices 𝑙$l$ and 𝑟$r$ (1≤𝑙≤𝑟≤𝑛$1\le l\le r\le n$);
• For every 𝑖$i$ that respects 𝑙≤𝑖≤𝑟$l\le i\le r$, change 𝑎𝑖$a_i$ to the opposite. That is, 𝑎𝑖:=1−𝑎𝑖$a_i:=1-a_i$;
• For every 𝑖$i$ that respects either 1≤𝑖<𝑙$1\le i<l$ or 𝑟<𝑖≤𝑛$r<i\le n$, change 𝑏𝑖$b_i$ to the opposite. That is, 𝑏𝑖:=1−𝑏𝑖$b_i:=1-b_i$.

Your task is to determine if this is possible, and if it is, to find such an appropriate chain of operations. The number of operations should not exceed 𝑛+5$n+5$. It can be proven that if such chain of operations exists, one exists with at most 𝑛+5$n+5$ operations.

Input

Each test consists of multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤105$1\le t\le {10}^5$) — the number of test cases. The description of test cases follows.

The first line of each test case contains a single integer 𝑛$n$ (2≤𝑛≤2⋅105$2\le n\le 2\cdot {10}^5$) — the length of the strings.

The second line of each test case contains a binary string 𝑎$a$, consisting only of characters 0 and 1, of length 𝑛$n$.

The third line of each test case contains a binary string 𝑏$b$, consisting only of characters 0 and 1, of length 𝑛$n$.

It is guaranteed that sum of 𝑛$n$ over all test cases doesn't exceed 2⋅105$2\cdot {10}^5$.

Output

For each testcase, print first "YES" if it's possible to make all the elements of both strings equal to 0$0$. Otherwise, print "NO". If the answer is "YES", on the next line print a single integer 𝑘$k$ (0≤𝑘≤𝑛+5$0\le k\le n+5$) — the number of operations. Then 𝑘$k$ lines follows, each contains two integers 𝑙$l$ and 𝑟$r$ (1≤𝑙≤𝑟≤𝑛$1\le l\le r\le n$) — the description of the operation.

If there are several correct answers, print any of them.

Note

In the first test case, we can perform one operation with 𝑙=2$l=2$ and 𝑟=2$r=2$. So 𝑎2:=1−1=0$a_2:=1-1=0$ and string 𝑎$a$ became equal to 000. 𝑏1:=1−1=0$b_1:=1-1=0$, 𝑏3:=1−1=0$b_3:=1-1=0$ and string 𝑏$b$ became equal to 000.

In the second and in the third test cases, it can be proven that it's impossible to make all elements of both strings equal to 0$0$.

In the fourth test case, we can perform an operation with 𝑙=1$l=1$ and 𝑟=2$r=2$, then string 𝑎$a$ became equal to 01, and string 𝑏$b$ doesn't change. Then we perform an operation with 𝑙=2$l=2$ and 𝑟=2$r=2$, then 𝑎2:=1−1=0$a_2:=1-1=0$ and 𝑏1=1−1=0$b_1=1-1=0$. So both of string 𝑎$a$ and 𝑏$b$ became equal to 00.

In the fifth test case, we can perform an operation with 𝑙=1$l=1$ and 𝑟=1$r=1$. Then string 𝑎$a$ became equal to 011 and string 𝑏$b$ became equal to 100. Then we can perform an operation with 𝑙=2$l=2$ and 𝑟=3$r=3$, so both of string 𝑎$a$ and 𝑏$b$ became equal to 000.