D. Простая задача про ПСП
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Скобочная последовательность называется правильной, если в неё можно вставить символы $$$+$$$ и $$$1$$$ так, чтобы получить корректное арифметическое выражение. Например, последовательности (())(), () и (()(())) являются правильными, а )(, (() и (()))( — нет. Будем называть правильную скобочную последовательность ПСП.

Вы можете выполнять следующую операцию над любой строкой $$$b$$$, являющейся ПСП:

  • выбрать любые две непересекающиеся непустые подстроки$$$^{\text{∗}}$$$ строки $$$b$$$, которые являются ПСП, и поменять эти две подстроки местами.

Более формально, пусть $$$m$$$ — длина строки $$$b$$$. Вы можете выполнить над $$$b$$$ следующую операцию:

  • выбрать индексы $$$1 \le l_1 \lt r_1 \lt l_2 \lt r_2 \le m$$$ так, что подстроки $$$b[{l_1..r_1}]$$$ и $$$b[l_2..r_2]$$$ обе являются ПСП, и поменять эти подстроки местами. После этого строка $$$b$$$ становится равной $$$b_1 \ldots b_{l_1-1} b_{l_2} b_{l_2+1}\ldots b_{r_2} b_{r_1+1}\ldots b_{l_2-1} b_{l_1} b_{l_1+1}\ldots b_{r_1}b_{r_2+1} \ldots b_m$$$.

Вам даны две строки $$$s$$$ и $$$t$$$ длины $$$n$$$ ($$$n$$$ чётно), причём и $$$s$$$, и $$$t$$$ являются ПСП.

Определите, можно ли преобразовать $$$s$$$ в $$$t$$$, используя описанную выше операцию любое количество раз.

$$$^{\text{∗}}$$$Строка $$$a$$$ является подстрокой строки $$$b$$$, если $$$a$$$ может быть получена из $$$b$$$ удалением нескольких (возможно, ни одного или всех) символов с начала и нескольких (возможно, ни одного или всех) символов с конца.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$4\leq n\leq 5\cdot 10^5$$$, $$$n$$$ чётно).

Вторая строка каждого набора входных данных содержит строку $$$s$$$ длины $$$n$$$, такую, что $$$s$$$ является ПСП.

Третья строка каждого набора входных данных содержит строку $$$t$$$ длины $$$n$$$, такую, что $$$t$$$ является ПСП.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$5\cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите «YES», если $$$s$$$ можно преобразовать в $$$t$$$, и «NO» в противном случае.

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
5
4
()()
()()
4
()()
(())
6
(())()
()(())
8
(()()())
()()(())
8
()()(())
()(()())
Выходные данные
YES
NO
YES
NO
YES
Примечание

В первом наборе входных данных две строки уже совпадают.

В третьем наборе входных данных можно выбрать $$$l_1=1,r_1=4,l_2=5,r_2=6$$$ и преобразовать $$$s$$$ в $$$t$$$.

Вот визуализация операции, выполненной в этом случае:

$$$\color{red}{(())}\color{blue}{()}\rightarrow\color{blue}{()}\color{red}{(())}$$$