Complementary XOR
Contest: CodeTON Round 3 (Div. 1 + Div. 2, Rated, Prizes!)
Difficulty rating: 1400
Tags: constructive algorithms, implementation

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$$$. Unfortunately, you can modify the contents of these strings using only the following operation:

- You choose two indices $$$l$$$ and $$$r$$$ ($$$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, $$$a_i := 1 - a_i$$$;
- For every $$$i$$$ that respects either $$$1 \le i < l$$$ or $$$r < i \le n$$$, change $$$b_i$$$ to the opposite. That is, $$$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 $$$n + 5$$$. It can be proven that if such chain of operations exists, one exists with at most $$$n + 5$$$ operations.

Input format:
Each test consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 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 \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 \cdot 10^5$$$.

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

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

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
In the first test case, we can perform one operation with $$$l = 2$$$ and $$$r = 2$$$. So $$$a_2 := 1 - 1 = 0$$$ and string $$$a$$$ became equal to 000. $$$b_1 := 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$$$.

In the fourth test case, we can perform an operation with $$$l = 1$$$ and $$$r = 2$$$, then string $$$a$$$ became equal to 01, and string $$$b$$$ doesn't change. Then we perform an operation with $$$l = 2$$$ and $$$r = 2$$$, then $$$a_2 := 1 - 1 = 0$$$ and $$$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 $$$l = 1$$$ and $$$r = 1$$$. Then string $$$a$$$ became equal to 011 and string $$$b$$$ became equal to 100. Then we can perform an operation with $$$l = 2$$$ and $$$r = 3$$$, so both of string $$$a$$$ and $$$b$$$ became equal to 000.

Example input:
5
3
010
101
2
11
10
4
1000
0011
2
10
10
3
111
111

Example output:
YES
1
2 2
NO
NO
YES
2
1 2
2 2
YES
2
1 1
2 3

Editorial:
For each operation, the interval changed by a sequence and b sequence is complementary, so you must judge whether all $$$[a_i=b_i]$$$ are the same at the beginning. If they are different, you can't have a solution.
Now, if $$$a = \neg b$$$, we can do an operation on $$$a$$$ and have $$$a=b$$$. Now suppose $$$a_i=b_i=1$$$ for some $$$i$$$ and try to make $$$a_i=b_i=0$$$ without changing anything else. If $$$i>1$$$, then this is very simple, we can just do an operation with $$$(1,i)$$$ and an operation on $$$(1,i-1)$$$. If $$$i=1$$$ we can make $$$(1,n)$$$ and $$$(2,n)$$$. Since $$$n>1$$$, this can always be done, thus we found a solution using $$$O(2 \cdot n)$$$ operations. To optimize it to only use $$$O(n)$$$ operations, note that we only care about the parity of the number of operations did at any index.