CF1837D Bracket Coloring

一个“正规括号序列”是指可以通过在原序列的括号之间插入字符 $1$ 和 $+$，将其转化为一个合法的算术表达式的括号序列。例如： - 括号序列 "()()" 和 "(())" 是正规括号序列（对应的表达式分别为 "(1)+(1)" 和 "((1+1)+1)"）； - 括号序列 ")(", "(" 和 ")" 不是正规括号序列。 如果一个括号序列满足以下任一条件，则称其为“美丽括号序列”： - 它是一个正规括号序列； - 如果将该序列的字符顺序反转后，它变成了一个正规括号序列。 例如，括号序列 "()()"、"(())"、")))((("、"))()((" 都是美丽括号序列。 现在给定一个括号序列 $s$，你需要对其进行染色，要求如下： - 每个括号都要被染上一种颜色； - 每种颜色至少要染到一个括号； - 对于每种颜色，将所有染成该颜色的括号，按照它们在原序列中的顺序写出来，得到的括号序列必须是美丽括号序列。 请你用最少的颜色数对给定的括号序列 $s$ 进行染色，满足上述要求。如果无法做到，输出 $-1$。

第一行包含一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例包含两行。第一行包含一个整数 $n$（$2 \le n \le 2 \cdot 10^5$），表示括号序列的长度。第二行包含一个长度为 $n$ 的字符串 $s$，其中每个字符都是 "(" 或 ")"。 输入还满足：所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每个测试用例，按如下要求输出答案： - 如果无法按照题意对括号进行染色，输出 $-1$； - 否则输出两行。第一行输出一个整数 $k$（$1 \le k \le n$），表示所需的最小颜色数。第二行输出 $n$ 个整数 $c_1, c_2, \dots, c_n$（$1 \le c_i \le k$），其中 $c_i$ 表示第 $i$ 个括号的颜色。如果有多种方案，输出任意一种均可。

由 ChatGPT 4.1 翻译