У вас есть две бинарные строки $$$a$$$ и $$$b$$$ длины $$$n$$$. Вы хотите сделать все элементы обеих строк равными $$$0$$$. К сожалению, вы можете изменять содержимое этих строк, используя только следующую операцию:
Ваша задача — определить, возможно ли это, и если да, то найти такую подходящую последовательность операций. Количество операций не должно превышать $$$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$$$.
Для каждого набора входных данных выведите сначала «YES», если возможно сделать все элементы обеих строк равными $$$0$$$. В противном случае выведите «NO». Если ответ «YES», в следующей строке выведите одно целое число $$$k$$$ ($$$0 \le k \le n + 5$$$) — количество операций. Далее должны следовать $$$k$$$ строк, каждая из которых содержит два целых числа $$$l$$$ и $$$r$$$ ($$$1 \le l \le r \le n$$$) — описание операции.
Если правильных ответов несколько, выведите любой из них.
5301010121110410000011210103111111
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.
Название |
---|