AT_utpc2022_i Which must be deleted?

由仅包含 `(`、`)` 的字符串，如果满足以下任一条件，被称为“正确括号序列”： - 空字符串。 - 存在一个“正确括号序列” $A$，将 `(`、$A$、`)` 按此顺序连接而成的字符串。 - 存在不为空的“正确括号序列” $A,\ B$，将 $A,\ B$ 按此顺序连接而成的字符串。 给你一个长度为 $4N$、仅包含 `(` 和 `)` 的字符串 $S$，以及 $2N$ 个整数对 $(L_i, R_i)\ (1 \leq L_i < R_i \leq 4N)$。其中，$(L_1, L_2, \dots, L_{2N})$ 是 $1,2,\dots,2N$ 的一个排列，$(R_1, R_2, \dots, R_{2N})$ 是 $2N+1,2N+2,\dots,4N$ 的一个排列。 按照 $i=1,2,\dots,2N$ 的顺序，对于每组 $(L_i, R_i)$，可以任选 $S$ 的 $L_i$ 或 $R_i$ 位置打标记。将所有被标记的字符按在 $S$ 中出现的顺序依次读出，得到一个长度为 $2N$ 的字符串 $S'$。 请判断，是否存在一种方式使得 $S'$ 是“正确括号序列”。 请对 $T$ 组测试用例分别作答。

输入按以下格式从标准输入读入： > $T$ > $\mathrm{case}_1$ > $\vdots$ > $\mathrm{case}_T$ 每个测试用例的格式如下： > $N$ > $S$ > $L_1\ R_1$ > $L_2\ R_2$ > $\vdots$ > $L_{2N}\ R_{2N}$

请输出 $T$ 行。对于第 $i$ 个测试用例，如果 $S'$ 存在一种构造方式使其成为“正确括号序列”，则输出 `Yes`，否则输出 `No`。

### 样例解释 1 对于第 $1$ 个测试用例，如果选择 $L_1=1$ 位置和 $R_2=4$ 位置，则 $S'$ 为 `()`，它是“正确括号序列”。 对于第 $2$ 个测试用例，无论如何选择，$S'$ 都不可能成为“正确括号序列”。 ### 数据范围与约定 - 输入的所有数值均为整数。 - $1 \leq T \leq 1000$ - $1 \leq N \leq 2000$ - $S$ 是长度为 $4N$ 的、仅包含 `(`、`)` 的字符串。 - $1 \leq L_i \leq 2N < R_i \leq 4N$ - $(L_1,L_2,\dots,L_{2N})$ 是 $1,2,\dots,2N$ 的一个排列。 - $(R_1,R_2,\dots,R_{2N})$ 是 $2N+1,2N+2,\dots,4N$ 的一个排列。 - 单次输入内所有测试用例，$N$ 的总和不超过 $2000$。 由 ChatGPT 5 翻译