← 返回题目列表

Codeforces · 1750/C

C. 互补异或

中文机器翻译题面 查看原题

您有两个长度为 $$$n$$$ 的二进制字符串 $$$a$$$ 和 $$$b$$$。您希望使两个字符串的所有元素都等于 $$$0$$$。不幸的是,您只能使用以下操作来修改这些字符串的内容:

- 您选择两个索引 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$);
- 对于每个尊重 $$$l \le i \le r$$$ 的 $$$i$$$,将 $$$a_i$$$ 更改为相反的值。即 $$$a_i := 1 - a_i$$$;
- 对于每个遵循 $$$1 \le i < l$$$ 或 $$$r < i \le n$$$ 的 $$$i$$$,将 $$$b_i$$$ 更改为相反的值。也就是说,$$$b_i := 1 - b_i$$$。

您的任务是确定这是否可行,如果可行,则找到这样一个合适的操作链。操作次数不应超过 $$$n + 5$$$。可以证明,如果存在这样的操作链,则最多存在 $$$n + 5$$$ 操作。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 10^5$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — 字符串的长度。

每个测试用例的第二行包含一个二进制字符串$$$a$$$,仅由字符0和1组成,长度为$$$n$$$。

每个测试用例的第三行包含一个二进制字符串$$$b$$$,仅由字符0和1组成,长度为$$$n$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2 \cdot 10^5$$$。

输出

对于每个测试用例,如果可以使两个字符串的所有元素等于 $$$0$$$,则首先打印“YES”。否则,打印“NO”。如果答案为“是”,则在下一行打印单个整数 $$$k$$$ ($$$0 \le k \le n + 5$$$) — 操作数。然后是 $$$k$$$ 行,每行包含两个整数 $$$l$$$ 和 $$$r$$$ ($$$1 \le l \le r \le n$$$) — 操作的描述。

如果有多个正确答案,请打印其中任何一个。

示例

输入 #1

5
3
010
101
2
11
10
4
1000
0011
2
10
10
3
111
111

输出 #1

YES
1
2 2
NO
NO
YES
2
1 2
2 2
YES
2
1 1
2 3

注意

在第一个测试用例中,我们可以使用 $$$l = 2$$$ 和 $$$r = 2$$$ 执行一个操作。因此 $$$a_2 := 1 - 1 = 0$$$ 和字符串 $$$a$$$ 等于 000。$$$b_1 := 1 - 1 = 0$$$, $$$b_3 := 1 - 1 = 0$$$ 和字符串 $$$b$$$ 等于 000。

在第二个和第三个测试用例中,可以证明不可能使两个字符串的所有元素都等于$$$0$$$。

在第四个测试用例中,我们可以执行 $$$l = 1$$$ 和 $$$r = 2$$$ 的操作,然后字符串 $$$a$$$ 变为等于 01,而字符串 $$$b$$$ 不变。然后我们执行 $$$l = 2$$$ 和 $$$r = 2$$$ 的操作,然后 $$$a_2 := 1 - 1 = 0$$$ 和 $$$b_1 = 1 - 1 = 0$$$。所以字符串 $$$a$$$ 和 $$$b$$$ 都等于 00。

在第五个测试用例中,我们可以执行 $$$l = 1$$$ 和 $$$r = 1$$$ 的操作。那么字符串$$$a$$$就等于011,字符串$$$b$$$就等于100。然后我们可以进行$$$l = 2$$$和$$$r = 3$$$的运算,所以字符串$$$a$$$和$$$b$$$都等于000。