#P18232. Brackets

Brackets

Brackets

给定一个长度为 nn 的字符串 ss,其中只含四种括号:圆括号 ()、方括号 []、花括号 {} 和尖括号 <>。

合法括号串递归定义如下:

  • 空串是合法括号串。
  • 若 A,BA,B 是合法括号串,则它们的拼接 ABAB 也是合法括号串。
  • 若 AA 是合法括号串,则 (A)(A)、[A][A]、{A}\{A\}、⟨A⟩\langle A\rangle 都是合法括号串。

另给出 mm 个区间 [li,ri][l_i,r_i]。第 ii 个对象是子串 slisli+1⋯sris_{l_i}s_{l_i+1}\cdots s_{r_i},下标从 11 开始。

你可以将这些对象中的若干个分成若干对。每一对包含两个不同编号的对象,而且每个对象最多出现在一对中。对于每一对,可以自行选择两个对象的先后顺序;按该顺序拼接得到的字符串必须是合法括号串。

求最多能得到多少对。

即使两个区间完全相同,它们仍是不同编号的对象,可以分别使用。区间之间允许重叠;限制针对对象编号,而非原串中的字符位置。

输入格式

第一行一个整数 TT,表示测试用例数。

每个测试用例:

  • 第一行两个整数 n,mn,m。
  • 第二行一个长度为 nn 的字符串 ss。
  • 接下来 mm 行,第 ii 行两个整数 li,ril_i,r_i。

数据范围:

  • 1≤T≤1041\le T\le 10^4;
  • 1≤n,m≤5×1051\le n,m\le 5\times10^5;
  • 1≤li≤ri≤n1\le l_i\le r_i\le n;
  • ss 中每个字符均属于四种左右括号;
  • 同一输入文件所有测试用例的 nn 之和不超过 5×1055\times10^5,mm 之和也不超过 5×1055\times10^5。

输出格式

每个测试用例输出一行一个整数,表示最多得到的对数。

样例

4
8 1
()[]{}<>
3 6
2 6
)(
1 1
1 1
1 1
2 2
2 2
2 2
6 2
([)(])
1 3
4 6
22 8
([{}<<<<])>>>>([]){()}
3 8
11 14
1 10
3 4
19 22
20 21
17 20
21 22
0
3
0
2

第一个测试用例只有一个对象,即使该对象本身是合法括号串,也无法组成一对。

第二个测试用例中,三个对象是右圆括号,另外三个对象是左圆括号。每个左圆括号与一个右圆括号配对,按先左后右的顺序拼接,可以得到三对。

第三个测试用例的两个对象分别为 ([) 和 (]),无论按哪种顺序拼接,都不是合法括号串。

第四个测试用例的一种最优选择是将第 1,21,2 个对象配成一对,第 4,54,5 个对象配成一对;每对内部按这些编号的顺序拼接即可。