← 返回题目列表

Codeforces · 1685/C

C. 带来平衡

中文机器翻译题面 查看原题

Alina 有一个长度为 $$$2n$$$ 的括号序列 $$$s$$$,由 $$$n$$$ 左括号 '(' 和 $$$n$$$ 右括号 ')' 组成。由于她喜欢平衡,所以她想把这个括号序列变成平衡的括号序列。

在一次操作中,她可以反转 $$$s$$$ 的任何子字符串。

将 $$$s$$$ 转变为平衡括号序列所需的最少操作次数是多少?可以证明,最多 $$$n$$$ 次操作始终是可能的。

提醒一下,如果可以通过添加字符 + 和 1 将括号序列转换为有效的数学表达式,则该序列称为平衡的。例如,序列 (())()、() 和 (()(())) 是平衡的,而 )(、(() 和 (()))( 不是平衡的。

输入

输入的第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 10^5$$$)。

每个测试用例的第二行包含一个长度为$$$2n$$$的字符串$$$s$$$,由$$$n$$$左括号和$$$n$$$右括号组成。

所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,在第一行输出一个整数 $$$k$$$ $$$(0 \le k \le n)$$$ — 所需的最小操作数。

接下来的 $$$k$$$ 行的第 $$$i$$$ 行应包含两个整数 $$$l_i, r_i$$$ ($$$1 \le l_i \le r_i \le 2n$$$),表示在第 $$$i$$$ 操作中,Alina 将反转子字符串 $$$s_ls_{l+1} \ldots s_{r-1}s_r$$$。这里从$$$1$$$开始计数。

如果有多个最小长度的操作序列将序列转换为平衡序列,则可以输出其中任何一个。

示例

输入 #1

3
2
(())
5
())((()))(
6
())((()))(()

输出 #1

0
2
3 4
9 10
1
2 11

注意

在第一个测试用例中,字符串已经平衡。

在第二个测试用例中,字符串将按如下方式转换: ())((()))( $$$\to$$$ ()()(()))( $$$\to$$$ ()()(())(),其中最后一个字符串是平衡的。

在第三个测试用例中,字符串将被转换为 ((()))((())),这是平衡的。