正则括号序列是通过在序列的原始字符之间插入字符“1”和“+”可以将括号序列转换为正确的算术表达式。例如:
- 括号序列“()()”和“(())”是正则的(结果表达式是:“(1)+(1)”和“((1+1)+1)”);
- 括号序列“)(”、“(”和“)”不是。
如果满足以下条件之一,则括号序列被称为漂亮的:
- 这是一个常规的括号序列;
- 如果该序列中的字符顺序颠倒,则它成为常规的括号序列。
例如,括号序列“()()”、“(())”、“)))(((”、“))()((”很漂亮。
给你一个括号序列$$$s$$$。你必须以这样的方式给它上色:
- 每个括号都被着色为一种颜色;
- 对于每种颜色,至少有一个括号着色为该颜色;
- 对于每种颜色,如果您按照出现的顺序记下具有该颜色的括号序列,您将得到一个漂亮的括号序列。
根据这些约束将给定的括号序列 $$$s$$$ 着色为最少数量的颜色,或者报告这是不可能的。
输入
第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。
每个测试用例由两行组成。第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — $$$s$$$ 中的字符数。第二行包含 $$$s$$$ — 一个由 $$$n$$$ 字符组成的字符串,其中每个字符都是“(”或“)”。
对输入的附加约束:所有测试用例的 $$$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$$$ 括号的颜色。如果有多个答案,请打印其中任何一个。
示例
输入 #1
4 8 ((())))( 4 (()) 4 ))(( 3 (()
输出 #1
2 2 2 2 1 2 2 2 1 1 1 1 1 1 1 1 1 1 1 -1