← 返回题目列表

Codeforces · 1227/C

C. 凌乱

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

你厌倦了凌乱的房间,所以你决定清理它。

你的房间是一个括号序列$$$s=s_{1}s_{2}\dots s_{n}$$$,长度为$$$n$$$。该字符串的每个字符都是左括号“(”或右括号“)”。

在一次操作中,您可以选择 $$$s$$$ 的任何连续子字符串并将其反转。换句话说,您可以选择任何子字符串 $$$s[l \dots r]=s_l, s_{l+1}, \dots, s_r$$$ 并将其中元素的顺序更改为 $$$s_r, s_{r-1}, \dots, s_{l}$$$。

例如,如果您决定反转字符串 $$$s=$$$"((()))" 的子字符串 $$$s[2 \dots 4]$$$,则它将等于 $$$s=$$$"()(())"。

常规(又称平衡)括号序列是可以通过在序列的原始字符之间插入字符“1”和“+”来转换为正确的算术表达式的括号序列。例如,括号序列“()()”、“(())”是正则表达式(结果表达式为:“(1)+(1)”、“((1+1)+1)”),而“)(”和“(”则不是。

字符串 $$$s$$$ 的前缀是从位置 $$$1$$$ 开始的子字符串。例如,对于 $$$s=$$$"(())()",有 $$$6$$$ 前缀:“(”、“((”、“(()”、“(())”、“(())(”和“(())()”。

在你看来,一个整洁干净的房间 $$$s$$$ 是一个括号序列:

- 整个字符串 $$$s$$$ 是一个常规的括号序列;
- 并且该序列的 $$$k$$$ 前缀是规则的(包括整个 $$$s$$$ 本身)。

例如,如果$$$k = 2$$$,则“(())()”是一个整洁干净的房间。

您希望使用最多 $$$n$$$ 操作来使您的房间整洁干净。操作按顺序一个接一个地应用。

保证答案存在。请注意,您不需要最小化操作数量:找到任何方法在 $$$n$$$ 或更少的操作中实现所需的配置。

输入

第一行包含整数 $$$t$$$ ($$$1 \le t \le 100$$$) — 输入中测试用例的数量。然后是 $$$t$$$ 测试用例。

测试用例的第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \le k \le \frac{n}{2}, 2 \le n \le 2000$$$, $$$n$$$ 是偶数) — $$$s$$$ 的长度和所需的常规前缀数量。

测试用例的第二行包含长度为 $$$n$$$ 的 $$$s$$$ — 给定的括号序列。它仅包含“(”和“)”。

保证给定字符串中恰好有 $$$\frac{n}{2}$$$ 字符 '(' 和 $$$\frac{n}{2}$$$ 字符 ')'。

输入中所有测试用例的所有值 $$$n$$$ 的总和不超过 $$$2000$$$。

输出

对于每个测试用例打印一个答案。

在第一行打印整数 $$$m$$$ ($$$0 \le m \le n$$$) — 操作数。您不需要最小化$$$m$$$,任何值都合适。

在接下来的 $$$m$$$ 行中打印操作说明,每行应包含两个整数 $$$l,r$$$ ($$$1 \le l \le r \le n$$$),表示 $$$s[l \dots r]=s_{l}s_{l+1}\dots s_{r}$$$ 的单个反向操作。操作按顺序一个接一个地应用。

所有操作后最后的$$$s$$$应该是正则,也应该恰好是正则的$$$k$$$前缀(包括$$$s$$$)。

保证答案存在。如果有多个可能的答案,您可以打印任何一个。

示例

输入 #1

4
8 2
()(())()
10 3
))()()()((
2 1
()
2 1
)(

输出 #1

4
3 4
1 1
5 8
2 2
3
4 10
1 4
6 7
0
1
1 2

注意

在第一个示例中,最终序列是“()(()())”,其中两个前缀是常规的,“()”和“()(()())”。请注意,示例输出中除“5 8”之外的所有操作都是无用的(它们不会更改 $$$s$$$)。