P7938 「Wdcfr-1」Beautiful Array

在这个问题中，我们将由 `(` 和 `)` 组成的序列定义为“括号序列”。 *正规括号序列* 的定义如下： 1. `()` 是一个正规括号序列。 2. 如果 `A` 是一个正规括号序列，那么 `(A)` 也是一个正规括号序列。 3. 如果 `A` 和 `B` 是正规括号序列，那么 `AB` 也是一个正规括号序列。 例如：`()`, `(())` 和 `()()` 都是正规括号序列，但 `)(`, `()(` 不是。 特别地，在这个问题中，空序列**不是**一个正规括号序列。 现在，~~可爱的~~ Ran 给你一个长度为 $n$ 的括号序列 $s$。她希望你构造 $2 \cdot m$ 个**严格递增**的数组。我们将它们记作 $p_1,p_2,\cdots,p_{2m}$（你可以将其中任何一个留空）。你需要确保所有从 $1\sim n$ 的整数在这些数组中**恰好出现一次**。 一个数组 $p_i=\{r_1,r_2,\cdots,r_k\}$ 是*美丽的*，如果 $\{s_{r_1},s_{r_2},\cdots,s_{r_k}\}$ 是一个正规括号序列。 Ran 想知道是否有可能构造这些数组，使得 $2 \cdot m$ 个数组中至少 $m$ 个是“美丽数组”。

每个测试包含多个测试用例。 第一行包含一个整数 $T$，表示测试用例的数量。 对于每个测试用例，第一行包含两个整数 $n$ 和 $m$，第二行包含一个括号序列 $s$。

对于每个测试用例，输出一行。 如果可以构造这些数组，输出 $1$。否则输出 $0$。

### 解释 对于第一个测试用例，我们可以构造 $p_1=\{1,2\}$ 和 $p_2=\{\}$。所以 $p_1$ 是一个“美丽数组”。 对于第二个测试用例，很明显我们不能用两个数字构造 $99$ 个美丽数组。 ### 约束 $1\le T,n,m\le 200$。 题面翻译由 ChatGPT-4o 提供。