题目描述

Yousef 给了你一个长度为 $n$ 的序列 $s$，该序列仅由字符 '(' 和 ')' 组成。你最多可以执行以下操作一次：

• 选择 $s$ 的一个子串 $^*$ 并将其移除。然后，你可以将移除的字符逐个重新插入到剩下的字符串中的任意位置，每个字符的位置可任意选择，互不影响。

Yousef 想让你判断，是否可以通过最多执行一次上述操作之后，使得序列变为一个合法括号序列 $^\dagger$。

$^*$ 子串是字符串的一个连续子段。例如，"acab" 是 "abacaba" 的一个子串（从第 $3$ 位开始到第 $6$ 位结束），但 "aa" 或 "d" 不是该字符串的子串。所以，字符串 $s$ 从第 $l$ 位到第 $r$ 位的子串用 $s[l, r]= s_l s_{l+1} \dots s_r$ 表示。

$^\dagger$ 合法括号序列是可以通过在原括号序列各处插入若干个 $1$ 和 $+$，使其变为正确算数表达式的括号序列。例如：

• 括号序列 $\texttt{()()}$ 和 $\texttt{(())}$ 是合法的（插入后可得到：$\texttt{(1)+(1)}$ 和 $\texttt{((1+1)+1)}$）；
• 括号序列 $\texttt{)(}$、$\texttt{(}$ 和 $\texttt{)}$ 都不是合法的。

输入格式

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例组数。接下来的每组测试用例描述如下。

每组测试用例的第一行包含一个整数 $n$（$1 \le n \le 2 \cdot 10^5$），表示字符串 $s$ 的长度。

第二行包含一个长度为 $n$ 仅由 '(' 和 ')' 组成的序列 $s$。

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

输出格式

每组测试用例，对于每个序列，如果能够通过最多一次操作使其变为合法括号序列，输出 "YES"；否则输出 "NO"。

你可以输出任意大小写形式，例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为正确答案。

样例

6
2
()
2
)(
3
(((
6
())(()
4
(()(
5
)()()

YES
YES
NO
YES
NO
NO

样例说明

在第一个测试用例中，字符串 $s$ 已经是一个合法括号序列，因此输出 "YES"。

在第二个测试用例中，我们可以移除子串 $s[2, 2] = \texttt{(}$，并将其插入到字符串的开头，得到 $s = \texttt{()}$，因此输出 "YES"。

在第三个测试用例中，无论如何操作都无法得到一个合法括号序列，因此输出 "NO"。

在第四个测试用例中，我们可以选择子串 $s[3, 4] = \texttt{)(}$，将其移除，然后如下方式将字符重新插入：

$$\texttt{()}{\color{red}{\texttt{)(}}}\texttt{()} \to \texttt{()()} \to {\color{green}{\texttt{(}}}\texttt{()()}{\color{green}{\texttt{)}}}$$

因此我们得到了一个合法括号序列，答案为 "YES"。

由 ChatGPT 5 翻译

来源

Codeforces 2227B，英文题名 Party Monster。