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 翻译