Вы - ученый, исследующий алгоритмы на бинарных деревьях. Бинарное дерево - это структура данных, состоящая из узлов ветвления и листов. Каждый узел ветвления имеет левого и правого сына, каждый сын - или узел ветвления, или лист. Корнем дерева является узел ветвления, у которого нет родителя. Вы готовитесь к презентации, где Вам следует создать изображение бинарных деревьев при помощи программного обеспечения. Вы уже создали картинку, на которой изображено бинарное дерево, состоящее из одного узла ветвления и двух листьев (\textit{\textbf{Рисунок 1}}). Однако внезапно у Вас сломалась функция, позволяющая программе создавать рисунок. Вы очень расстроились, так как через пять часов Вам следует сделать презентацию перед большой аудиторией. Вы решили создать изображение бинарных деревьев, используя только функции копирования, сжатия и вставки. То есть Вы можете совершать только следующие два типа операций: \begin{itemize} \item Скопировать текущую фигуру в буфер обмена (фигура копируется в буфер, предыдущее его содержимое удаляется). \item Вставить скопированную фигуру (с масштабированием, если необходимо), прикрепив корень вставленной фигуры к листу текущей (скопированную фигуру можно вставлять много раз). \end{itemize} Более того, Вы решили сделать фигуру, совершив наименьшее количество операций вставки, поскольку именно операция вставки требует много времени. Ваша задача - найти наименьшее количество операций вставки для создания заданной фигуры. \includegraphics{https://static.e-olymp.com/content/2d/2dd5bea485205c5e57cc2a7faa0d9621d9fd5cc7.jpg} \textit{\textbf{Рисунок 1}}: начальное состояние Ответ на пример \textbf{1} (\textit{\textbf{Рисунок 4}}) равен \textbf{3}, так как требуемую фигуру можно получить совершив следующий минимум операций. \includegraphics{https://static.e-olymp.com/content/0d/0d816b8f38e197e479945db171e0f09be92b3aa2.jpg} \textit{\textbf{Рисунок 2}}: промежуточная часть \textbf{1} \includegraphics{https://static.e-olymp.com/content/d3/d3ce6e963e171ac28131106463daba58fae9dcb0.jpg} \textit{\textbf{Рисунок 3}}: промежуточная часть \textbf{2} \includegraphics{https://static.e-olymp.com/content/11/114a423b587f750f62873fa6345cf96e1af7243f.jpg} \textit{\textbf{Рисунок 4}}: Цель \InputFile Входная строка задает бинарное дерево. Грамматика выражения задается следующей \textbf{БНФ}: \textbf{::= | "(" ")"} \textbf{::= "()"} Входные данные удовлетворяют указанному синтаксису. Считайте, что каждое входное дерево имеет хотя бы один и не более \textbf{10^5} узлов ветвления. \OutputFile Наименьшее количество операций вставки, которое следует выполнить для получения заданного бинарного дерева.