D. Раскраска скобок
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «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$$$-й скобки. Если ответов несколько, выведите любой из них.
Пример
Входные данные
4
8
((())))(
4
(())
4
))((
3
(()
Выходные данные
2
2 2 2 1 2 2 2 1
1
1 1 1 1
1
1 1 1 1
-1