#646. P7938 「Wdcfr-1」Beautiful Array

P7938 「Wdcfr-1」Beautiful Array

题目描述

在这个问题中,我们将由 ( 和 ) 组成的序列定义为“括号序列”。

正规括号序列 的定义如下:

  1. () 是一个正规括号序列。
  2. 如果 A 是一个正规括号序列,那么 (A) 也是一个正规括号序列。
  3. 如果 A 和 B 是正规括号序列,那么 AB 也是一个正规括号序列。

例如:(), (()) 和 ()() 都是正规括号序列,但 )(, ()( 不是。

特别地,在这个问题中,空序列不是一个正规括号序列。

现在,可爱的 Ran 给你一个长度为 nn 的括号序列 ss。她希望你构造 2⋅m2 \cdot m 个严格递增的数组。我们将它们记作 p1,p2,⋯ ,p2mp_1,p_2,\cdots,p_{2m}(你可以将其中任何一个留空)。你需要确保所有从 1∼n1\sim n 的整数在这些数组中恰好出现一次。

一个数组 pi={r1,r2,⋯ ,rk}p_i=\{r_1,r_2,\cdots,r_k\} 是美丽的,如果 {sr1,sr2,⋯ ,srk}\{s_{r_1},s_{r_2},\cdots,s_{r_k}\} 是一个正规括号序列。

Ran 想知道是否有可能构造这些数组,使得 2⋅m2 \cdot m 个数组中至少 mm 个是“美丽数组”。

输入格式

每个测试包含多个测试用例。

第一行包含一个整数 TT,表示测试用例的数量。

对于每个测试用例,第一行包含两个整数 nn 和 mm,第二行包含一个括号序列 ss。

输出格式

对于每个测试用例,输出一行。

如果可以构造这些数组,输出 11。否则输出 00。

样例

2
2 1
()
2 99
()
1
0

题目来源:洛谷 P7938