如果可以通过在序列中插入字符 $$$+$$$ 和 $$$1$$$ 来获得正确的算术表达式,则该括号序列称为正则序列。例如,序列 (())(), () 和 (()(())) 是有规律的,而 )(, (() 和 (()))( 不是。让我们调用一个常规的括号序列 苏格兰皇家银行.
您可以对任何 RBS 字符串 $$$b$$$ 执行以下操作 —
- 选择任意两个 不相交, 非空 $$$b$$$ 的子串$$$^{\text{*}}$$$ 是 RBS 并交换两个子串。
更正式地说,令 $$$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]$$$ 都是 RBS 并交换这些子字符串。字符串 $$$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$$$ 都是 RBS。
确定是否可以使用上述操作将 $$$s$$$ 转换为 $$$t$$$ 任何 次数。
$$$^{\text{*}}$$$ 字符串 $$$a$$$ 是字符串 $$$b$$$ 的子字符串,如果 $$$a$$$ 可以通过从 $$$b$$$ 删除开头的几个(可能是零个或全部)字符和从末尾删除几个(可能是零个或全部)字符来获得。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$4\leq n\leq 5\cdot 10^5$$$, $$$n$$$ 是 甚至).
每个测试用例的第二行包含一个长度为 $$$n$$$ 的字符串 $$$s$$$,使得 $$$s$$$ 是一个 RBS。
每个测试用例的第三行包含一个长度为 $$$n$$$ 的字符串 $$$t$$$,使得 $$$t$$$ 是一个 RBS。
保证所有测试用例的 $$$n$$$ 总和不超过 $$$5\cdot 10^5$$$。
输出
对于每个测试用例,打印“是" 如果 $$$s$$$ 可以转换为 $$$t$$$,并且 "NO”否则。
您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是", "是“,和”是”将被视为积极响应。
示例
输入复制
54()()()()4()()(())6(())()()(())8(()()())()()(())8()()(())()(()())
输出复制
YESNOYESNOYES
注意
在第一个测试用例中,两个字符串已经相同。
在第三个测试用例中,我们可以选择 $$$l_1=1,r_1=4,l_2=5,r_2=6$$$ 并将 $$$s$$$ 转换为 $$$t$$$。
这是在这种情况下执行的操作的可视化 -
$$$\颜色{红色}{(())}\颜色{蓝色}{()}\rightarrow\颜色{蓝色}{()}\颜色{红色}{(())}$$$