在荒野深处,Zhily和Jily发现了两个由括号组成的序列。每个序列都带有一些逻辑结构,但它们本身都不一定是规则的括号序列。他们发现通过交换两个序列之间的括号,可以修复它们。他们希望通过在两个序列之间交换括号来使两个序列成为常规括号序列。
常规括号序列是由“(”和“)”组成的序列,通过在序列中插入任意次数的 1 和 + 可以将其转换为有效的数学表达式。例如,序列“()(()())”是常规括号序列,而“())((”或“(()”不是常规括号序列。
给定两个括号序列 $$$a$$$ 和 $$$b$$$ 甚至 长度$$$n$$$。您可以多次执行以下操作:
- 选择一个位置 $$$i$$$ ($$$1 \leq i \leq n$$$) 并交换 $$$a_i$$$ 和 $$$b_i$$$。
确定是否可以将 $$$a$$$ 和 $$$b$$$ 都转换为常规括号序列。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \leq n \leq 2\cdot 10^5$$$, $$$n$$$ 是偶数) — 字符串 $$$a$$$ 和 $$$b$$$ 的长度。
每个测试用例的第二行包含一个长度为 $$$n$$$ 的序列 $$$a$$$,仅由字符“(”和“)”组成。
每个测试用例的第三行包含一个长度为 $$$n$$$ 的序列 $$$b$$$,仅由字符“(”和“)”组成。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。
输出
对于每个测试用例,如果可以将 $$$a$$$ 和 $$$b$$$ 都转换为常规括号序列,则输出“YES”,否则输出“NO”。您可以在任何情况下输出“YES”和“NO”(例如,“yES”、“yes”和“Yes”将被识别为肯定响应)。
示例
输入复制
72()()4))(((())4(((())))4()()(())6(((())()()))8()()()()(((())))4((((((((
输出复制
YESNONOYESYESYESNO
注意
在第一、第四和第六个测试用例中,$$$a$$$ 和 $$$b$$$ 最初都是规则的括号序列。
在第二个和第三个测试用例中,$$$a_1$$$ 或 $$$b_1$$$ 将为 ')',这使得它们不可能是正则的。
在第五个测试用例中,最终序列可能是 $$$\texttt{(((}\color{red}{\texttt{)}}\texttt{))}$$$ 和 $$$\texttt{()(}\color{red}{\texttt{(}}\texttt{))}$$$,其中要交换的括号为红色。