Задача E. Замена скобок: минимизация шагов

Автор:А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:128 Мб
Выходной файл:output.txt  

Условие

Рассмотрим последовательность из открывающихся и закрывающихся круглых скобок. Назовём такую последовательность скобочной. Скобочная последовательность называется правильной, если она может быть построена по следующим законам:

Примеры правильных скобочных последовательностей — "()", "((()))", "()()()", "((()())())(())". Неформально говоря, правильная скобочная последовательность — это последовательность скобок, которая может быть получена из некоторого арифметического выражения удалением из него всего, кроме скобок.

Рассмотрим следующий алгоритм: на каждом шаге выбирается подстрока скобочной последовательности и скобки в ней меняются на противоположные, то есть все символы '(' в этой подстроке заменяются на ')', а все символы ')' — на '('.

Требуется написать программу, которая по скобочной последовательности рассчитает минимальное количество шагов N, необходимое для превращения её в правильную.

Формат входного файла

Во входном файле содержится скобочная последовательность.

Формат выходного файла

В выходном файле должно содержаться число N, за которым следуют N пар чисел li ri, задающих позиции первого и последнего символа подстроки, в которой на i-ом шаге меняются скобки. Если существует несколько оптимальных решений, выведите любое из них.

Если решения не существует, выведите единственное число  − 1.

Ограничения

Длина исходной последовательности находится в диапазоне от 1 до 3000 символов

Примеры тестов

Входной файл (input.txt) Выходной файл (output.txt)
1
()
0
2
))((()
1
1 4
3
)((()((()((()(((
2
1 16
2 7

0.180s 0.017s 15