Правильная скобочная последовательность — это скобочная последовательность, которую можно превратить в корректное арифметическое выражение, вставив символы «1» и «+» между исходными символами. Например:
- скобочные последовательности «()()» и «(())» — правильные (из них можно получить выражения «(1)+(1)» и «((1+1)+1)»);
- скобочные последовательности «)(», «(» и «)» — неправильные.
Последовательность скобок называется красивой, если выполняется одно из следующих условий:
- она является правильной скобочной последовательностью;
- если порядок символов в этой последовательности изменить на противоположный, то она станет правильной скобочной последовательностью.
Например, скобочные последовательности «()()», «(())», «))((», «))()((» являются красивыми.
Вам дана последовательность скобок \(s\). Вы должны раскрасить ее таким образом, чтобы:
- каждая скобка была покрашена ровно в один цвет;
- для каждого цвета существует хотя бы одна скобка, покрашенная в этот цвет;
- для каждого цвета, если вы запишете последовательность скобок этого цвета в порядке, в котором они встречаются в строке, вы получите красивую скобочную последовательность.
Раскрасьте заданную последовательность скобок \(s\) в минимальное количество цветов в соответствии с этими ограничениями, или сообщите, что это невозможно.