CF1227C Messy

你厌倦了自己凌乱的房间，于是决定打扫一下。 你的房间是一个长度为 $n$ 的括号序列 $s=s_{1}s_{2}\dots s_{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$ 本身）是正规括号序列。 保证一定存在解。如果有多种方案，可以输出任意一种。

在第一个样例中，最终的序列是 "()(()())"，其中有两个前缀是正规括号序列，分别是 "()" 和 "()(()())"。注意，除了 "5 8" 以外，示例输出中的其他操作都是无用的（它们不会改变 $s$）。 由 ChatGPT 4.1 翻译